Home > Combinatorics, Geometry, IMO, Number theory > IMO 1995 Day 2

IMO 1995 Day 2


Problem 4 Find the maximum value of { x_{0}} for which there exists a sequence { x_{0},x_{1}\cdots ,x_{1995}} of positive reals with { x_{0} = x_{1995}}, such that

\displaystyle x_{i - 1} + \frac{2}{x_{i - 1}} = 2x_{i} + \frac {1}{x_{i}},

for all { i= 1,\cdots ,1995}.

Solution: First note that for positive real numbers {a,b} the equality

\displaystyle a+\frac{2}{a}=2b+\frac{1}{b}

is equivalent to

\displaystyle b \in \left\{ \frac{a}{2},\frac{1}{a}\right\},

and so we can conclude that

\displaystyle x_{i+1} \in \left\{ \frac{x_i}{2},\frac{1}{x_{i}}\right\}, i=0..1994.

Define the following functions {f,g :\Bbb{R}_+^* \rightarrow \Bbb{R}_+^*} by

\displaystyle f(x)=\frac{1}{x},\ g(x)=\frac{x}{2}.

Then we have {x_{i+1} \in \{f(x_i),g(x_i)\},\ i=0..1994}. So {x_0=x_{1995}=h(x_0)} where {h} is a composition of {1995} functions equal to {f} or {g}. We can give an inductive formula for such a composition of functions in the following way:

\displaystyle h(x)=g^{k_0}\circ f \circ g^{k_1} \circ f \circ.. \circ f \circ g^{k_n}(x)=\begin{cases} \displaystyle \frac{2^{k_1+k_3+k_5+...}}{2^{k_0+k_2+k_6+...}}\cdot x & n \text{ even} \\ & \\ \displaystyle \frac{2^{k_1+k_3+k_5+...}}{2^{k_0+k_2+k_6+...}}\cdot \frac{1}{x} & n \text{ odd} \end{cases}

where {g^{k}} means the composition of {g} with itself of {k} times and we take into account the possibility where {k_0=0} or {k_n=0} in which case {g^0} is the identity. Note that in fact {n} counts the number of times {f} appears in the composition. Also, we don’t take into account compositions of {f} with itself of more than one time, since {f} is an involution, moreover, all we need in our further considerations is to know the parity of {k_0+k_1+k_2+...}, which is an invariant even if we put compositions of an odd number of {f} in the formula.

Note that when {n} is even we would have {h(x_0)=x_0} and so we would need to have the equality

\displaystyle k_0+k_2+...=k_1+k_3+...

and we would end up with an even number of compositions. This contradicts the fact that we have {1995} compositions. Therefore the only valid case is when {n} is odd, and then {h(x_0)=x_0} implies

\displaystyle x_0= 2^{[(k_1+k_3+...)-(k_0+k_2+...)]/2},

which is maximal when {k_0+k_2+...} is minimal while {k_0+k_1+k_2+k_3+...} is maximal. This gives us two informations: first we need to minimize the number of {g}‘s on even position, which can be achieved if we keep only the position with {k_1}; secondly to maximize the sum of {k_i} we need to have the least number of {f}‘s in the composition and this can be achieved if we consider only one {f}.

Regarding our discussion above, the function {h} which maximizes {x_0} is {h(x)=f\circ g^{1994}} so the maximal value for {x_0} is

\displaystyle x_0 =2^{997}.

Problem 5 Let { ABCDEF} be a convex hexagon with { AB = BC = CD} and { DE = EF =FA}, such that { \angle BCD = \angle EFA = \frac {\pi}{3}}. Suppose { G} and { H} are points in the interior of the hexagon such that { \angle AGB=\angle DHE = \frac {2\pi}{3}}. Prove that { AG+ GB +GH +DH+HE \geq CF}.


Solution: This problem cannot be more simple if we make a good drawing. Construct outside the hexagon the equilateral triangles {ABX} and {DEY}. Due to the symmetry of the new figure with respect
to {BE} we have {CF=XY}. Because {G,H} are on the circumscribed circles of triangles {ABX} and {DEY}, respectively on the arcs which do not contain {X} and {Y}, respectively, we have

\displaystyle GX=GA+GB,\ HY=HD+HE,

so the inequality to be proven becomes the trivial inequality

\displaystyle GX +GH+HY \geq XY.

Problem 6 Let { p} be an odd prime number. How many { p}-element subsets { A} of { \{1,2,\cdots \ 2p\}} are there, the sum of whose elements is divisible by { p}?

Solution: Denote {X=\{1,2,..,p\},\ Y=\{p+1,...,2p\}}. For a set {A \subset X} we define a translation by a number {k \in X} to be

\displaystyle k+A=\{ y \in X : y \equiv k+x \mod p,\ \text{ for some }x \in A \},

which is a fancy way to write that we translate modulo {p} inside {X}. We define the same thing for {Y}.

Now note that if {P \subset \{1,2..,2p\}} and {|P|=p} then {P=X}, {P=Y} or {0<|P \cap X|,|P\cap Y|}. After these considerations consider {P \neq X,Y} and define

\displaystyle k+P= (k+(P\cap X))\cup (P\cap Y), k \in X.

Note that since {0<|P\cap X|< p} the sum of elements of {k+P} takes every residue modulo {P} out of which only one is good for our problem. We can define the equivalence relation on sets {P \subset \{1,2,..,2p\}} with {p} elements, {P \neq X,Y} as follows:

\displaystyle P \sim Q \Leftrightarrow (P\cap Y = Q \cap Y \text{ and } k+(P\cap X)=(Q \cap X) \text{ for some }k \in X).

This equivalence relation determines a partition of the family of {p}-elements subsets of {\{1,2,...,2p\}} different from {X,Y}. Each class of the partition has {p} elements, and from each class exactly one element satisfies the conditions of the problem. Therefore the answer of the problem is

\displaystyle \frac{{2p \choose p}-2}{p}+2

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: