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$