The 53rd International Mathematical Olympiad: Problems and Solutions

Given a triangle \( ABC \), let \( J \) be the center of the excircle opposite to the vertex \( A \). This circle is tangent to lines \( AB \), \( AC \), and \( BC \) at \( K \), \( L \), and \( M \), respectively. The lines \( BM \) and \( JF \) meet at \( F \), and the lines \( KM \) and \( CJ \) meet at \( G \). Let \( S \) be the intersection of \( AF \) and \( BC \), and let \( T \) be the intersection of \( AG \) and \( BC \). Prove that \( M \) is the midpoint of \( BC \).

We have \( KM\perp BJ \) hence \( BM \) is parallel to the bisector of \( \angle ABC \). Therefore \( \angle BMK=\frac12\angle ABC \) and \( \angle FMB=\frac12\angle ACB \). Denote by \( X \) the intersection of \( KM \) and \( FJ \). From the triangle \( FXM \) we derive: \[ \angle XFM=90^{\circ}-\angle FMB-\angle BMK=\frac12\angle BAC.\] The points \( K \) and \( M \) are symmetric with respect to the line \( FJ \) hence \( \angle KFJ=\angle JFM=\frac12\angle BAC=\angle KAJ \), therefore \( K \), \( J \), \( A \), and \( F \) belong to a circle which implies that \( \angle JFA=\angle JKA=90^{\circ} \) and \( KM\| AS \). The quadrilateral \( SKMA \) is a trapezoid and from \( \angle SMK=\angle AKM \) we obtain \( SM=AK \). Similarly, we get \( AL=TM \). Since \( AK=AL \) (tangents from \( A \) to the excircle) we get \( SM=TM \).

Let \( a_2 \), \( a_3 \), \( \dots \), \( a_n \) be positive real numbers that satisfy \( a_2\cdot a_3\cdots a_n=1 \). Prove that \[ \left(a_2+1\right)^2\cdot \left(a_3+1\right)^3\cdots \left(a_n+1\right)^n> n^n.\]

The inequality between arithmetic and geometric mean implies \[ \left(a_k+1\right)^k=\left(a_k+\frac1{k-1}+\frac1{k-1}+\cdots+\frac1{k-1}\right)^k \geq k^k\cdot a_k\cdot \frac1{(k-1)^{k-1}}=\frac{k^k}{(k-1)^{k-1}}\cdot a_k.\] The inequality is strict unless \( a_k=\frac1{k-1} \). Multiplying analogous inequalities for \( k=2 \), \( 3 \), \( \dots \), \( n \) yields \[ \left(a_2+1\right)^2\cdot \left(a_3+1\right)^3\cdots \left(a_n+n\right)^n> \frac{2^2}{1^1}\cdot\frac{3^3}{2^2}\cdot \frac{4^4}{3^3}\cdots \frac{n^n}{(n-1)^{n-1}}\cdot a_2a_3\cdots a_n=n^n. \] The inequality is strict because at least one of \( a_2 \), \( \dots \), \( a_n \) has to be greater than or equal than \( 1 \) and thus \( a_k> \frac1{k-1} \) holds for at least one integer \( k\in\{2,\dots, n\} \).

The liar’s guessing game is a game played between two players \( A \) and \( B \). The rules of the game depend on two positive integers \( k \) and \( n \) which are known to both players.

At the start of the game the player \( A \) chooses integers \( x \) and \( N \) with \( 1\leq x\leq N \). Player \( A \) keeps \( x \) secret, and truthfully tells \( N \) to the player \( B \). The player \( B \) now tries to obtain information about \( x \) by asking player \( A \) questions as follows: each question consists of \( B \) specifying an arbitrary set \( S \) of positive integers (possibly one specified in some previous question), and asking \( A \) whether \( x \) belongs to \( S \). Player \( B \) may ask as many questions as he wishes. After each question, player \( A \) must immediately answer it with yes or no, but is allowed to lie as many times as she wants; the only restriction is that, among any \( k+1 \) consecutive answers, at least one answer must be truthful.

After \( B \) has asked as many questions as he wants, he must specify a set \( X \) of at most \( n \) positive integers. If \( x\in X \), then \( B \) wins; otherwise, he loses. Prove that:

(a) If \( n\geq 2^k \) then \( B \) has a winning strategy.

(b) There exists a positive integer \( k_0 \) such that for every \( k\geq k_0 \) there exists an integer \( n\geq 1.99^k \) for which \( B \) cannot guarantee a victory.

The game can be reformulated in an equivalent one: The player \( A \) chooses an element \( x \) from the set \( S \) (with \( |S|=N \)) and the player \( B \) asks the sequence of questions. The \( j \)-th question consists of \( B \) choosing a set \( D_j\subseteq S \) and player \( A \) selecting a set \( P_j\in\left\{ Q_j,Q_j^C\right\} \). The player \( A \) has to make sure that for every \( j\geq 1 \) the following relation holds: \[ x\in P_j\cup P_{j+1}\cup\cdots \cup P_{j+k}.\] The player \( B \) wins if after a finite number of steps he can choose a set \( X \) with \( |X|\leq n \) such that \( x\in X \).

(a) It suffices to prove that if \( N\geq 2^k+1 \) then the player \( B \) can determine a set \( S^{\prime}\subseteq S \) with \( |S^{\prime}|\leq N-1 \) such that \( x\in S^{\prime} \).

Assume that \( N\geq 2^n+1 \). In the first move \( B \) selects any set \( D_1\subseteq S \) such that \( |D_1|\geq 2^{k-1} \) and \( |D_1^C|\geq 2^{k-1} \). After receiving the set \( P_1 \) from \( A \), \( B \) makes the second move. The player \( B \) selects a set \( D_2\subseteq S \) such that \( |D_2\cap P_1^C|\geq 2^{k-2} \) and \( |D_2^C\cap P_1^C|\geq 2^{k-2} \). The player \( B \) continues this way: in the move \( j \) he/she chooses a set \( D_j \) such that \( |D_j\cap P_j^C|\geq 2^{k-j} \) and \( |D_j^C\cap P_j^C|\geq 2^{k-j} \).

In this way the player \( B \) has obtained the sets \( P_1 \), \( P_2 \), \( \dots \), \( P_k \) such that \( \left(P_1\cup \cdots \cup P_k\right)^C\geq 1 \). Then \( B \) chooses the set \( D_{k+1} \) to be a singleton containing any element outside of \( P_1\cup\cdots \cup P_k \). There are two cases now:

• \( 1^{\circ} \) The player \( A \) selects \( P_{k+1}=D_{k+1}^C \). Then \( B \) can take \( S^{\prime}=S\setminus D_{k+1} \) and the statement is proved.

• \( 2^{\circ} \) The player \( A \) selects \( P_{k+1}=D_{k+1} \). Now the player \( B \) repeats the previous procedure on the set \( S_1=S\setminus D_{k+1} \) to obtain the sequence of sets \( P_{k+2} \), \( P_{k+3} \), \( \dots \), \( P_{2k+1} \). The following inequality holds: \[ \left|S_1\setminus \left(P_{k+2}\cdots P_{2k+1}\right)\right|\geq 1,\] since \( |S_1|\geq 2^k \). However, now we have \[ \left|\left(P_{k+1}\cup P_{k+2}\cup\cdots\cup P_{2k+1}\right)^C\right|\geq 1,\] and we may take \( S^{\prime}=P_{k+1}\cup \cdots \cup P_{2k+1} \).

(b) Let \( p \) and \( q \) be two positive integers such that \( 1.99< p< q< 2 \). Let us choose \( k_0 \) such that \[ \left(\frac{p}{q}\right)^{k_0}\leq 2\cdot \left(1-\frac{q}2\right)\quad\quad\quad\mbox{and}\quad\quad\quad p^k-1.99^k> 1.\] We will prove that for every \( k\geq k_0 \) if \( |S|\in\left(1.99^k, p^k\right) \) then there is a strategy for the player \( A \) to select sets \( P_1 \), \( P_2 \), \( \dots \) (based on sets \( D_1 \), \( D_2 \), \( \dots \) provided by \( B \)) such that for each \( j \) the following relation holds: \[ P_j\cup P_{j+1}\cup\cdots\cup P_{j+k}=S.\]

Assuming that \( S=\{1,2,\dots, N\} \), the player \( A \) will maintain the following sequence of \( N \)-tuples: \( (\mathbf{x})_{j=0}^{\infty}=\left(x_1^j, x_2^j, \dots, x_N^j\right) \). Initially we set \( x_1^0=x_2^0=\cdots =x_N^0=1 \). After the set \( P_j \) is selected then we define \( \mathbf x^{j+1} \) based on \( \mathbf x^j \) as follows: \[ x_i^{j+1}=\left\{\begin{array}{rl} 1,&\mbox{ if } i\in P_j \\ q\cdot x_i^j, &\mbox{ if } i\not\in P_j. \end{array}\right.\] The player \( A \) can keep \( B \) from winning if \( x_i^j\leq q^k \) for each pair \( (i,j) \). For a sequence \( \mathbf x \), let us define \( T(\mathbf x)=\sum_{i=1}^N x_i \). It suffices for player \( A \) to make sure that \( T\left(\mathbf x^j\right)\leq q^{k} \) for each \( j \).

Notice that \( T\left(\mathbf x^0\right)=N\leq p^k < q^k \).

We will now prove that given \( \mathbf x^j \) such that \( T\left(\mathbf x^j\right)\leq q^k \), and a set \( D_{j+1} \) the player \( A \) can choose \( P_{j+1}\in\left\{D_{j+1},D_{j+1}^C\right\} \) such that \( T\left(\mathbf x^{j+1}\right)\leq q^k \). Let \( \mathbf y \) be the sequence that would be obtained if \( P_{j+1}=D_{j+1} \), and let \( \mathbf z \) be the sequence that would be obtained if \( P_{j+1}=D_{j+1}^C \). Then we have \[ T\left(\mathbf y\right)=\sum_{i\in D_{j+1}^C} qx_i^j+\left|D_{j+1}\right|\] \[ T\left(\mathbf z\right)=\sum_{i\in D_{j+1}} qx_i^j+\left|D_{j+1}^C\right|.\] Summing up the previous two equalities gives: \[ T\left(\mathbf y\right)+T\left(\mathbf z\right)= q\cdot T\left(\mathbf x^j\right)+ N\leq q^{k+1}+ p^k, \mbox{ hence}\] \[ \min\left\{T\left(\mathbf y\right),T\left(\mathbf z\right)\right\}\leq \frac{q}2\cdot q^k+\frac{p^k}2\leq q^k,\] because of our choice of \( k_0 \).

Find all functions \( f:\mathbb Z\to\mathbb Z \) such that, for all integers \( a \), \( b \), \( c \) with \( a+b+c=0 \) the following equality holds: \[ f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a).\]

Substituting \( a=b=c=0 \) yields \( 3f(0)^2=6f(0)^2 \) which implies \( f(0)=0 \). Now we can place \( b=-a \), \( c=0 \) to obtain \( f(a)^2+f(-a)^2=2f(a)f(-a) \), or, equivalently \( \left(f(a)-f(-a)\right)^2=0 \) which implies \( f(a)=f(-a) \).

Assume now that \( f(a)=0 \) for some \( a\in\mathbb Z \). Then for any \( b \) we have \( a+b+(-a-b)=0 \) hence \( f(a)^2+f(b)^2+f(a+b)^2=2f(b)f(a+b) \), which is equivalent to \( \left(f(b)-f(a+b)\right)^2=0 \), or \( f(a+b)=f(b) \). Therefore if \( f(a)=0 \) for some \( a\neq 0 \), then \( f \) is a periodic function with period \( a \).

Placing \( b=a \) and \( c=2a \) in the original equation yields \( f(2a)\cdot \left(f(2a)-4f(a)\right)=0 \). Choosing \( a=1 \) we get \( f(2)=0 \) or \( f(2)=4f(1) \).

If \( f(2)=0 \), then \( f \) is periodic with period 2 and we must have \( f(n)=f(1) \) for all odd \( n \). It is easy to verify that for each \( c\in\mathbb Z \) the function \[ f(x)=\left\{\begin{array}{rl}0,& 2\mid n,\\ c, & 2\not\mid n\end{array}\right.\] satisfies the conditions of the problem.

Assume now that \( f(2)=4f(1) \) and that \( f(1)\neq 0 \). Assume that \( f(i)=i^2\cdot f(1) \) holds for all \( i\in\{1,2,\dots, n\} \) (it certainly does for \( i\in\{0,1,2\} \)). We place \( a=1 \), \( b=n \), \( c=-n-1 \) in the original equation to obtain: \[ f(1)^2+n^4f(1)^2+f(n+1)^2=2n^2f(1)^2+2(n^2+1)f(n+1)f(1)\] \[ \Leftrightarrow \quad\quad\quad \left(f(n+1)-(n+1)^2f(1)\right)\cdot \left(f(n+1)-(n-1)^2f(1)\right)=0.\]

If \( f(n+1)=(n-1)^2f(1) \) then setting \( a=n+1 \), \( b=1-n \), and \( c=-2 \) in the original equation yields \[ 2(n-1)^4f(1)^2+16f(1)^2=2\cdot 4\cdot 2(n-1)^2f(1)^2+2\cdot (n-1)^4f(1)\] which implies \( (n-1)^2=1 \) hence \( n=2 \). Therefore \( f(3)=f(1) \). Placing \( a=1 \), \( b=3 \), and \( c=4 \) into the original equation implies that \( f(4)=0 \) or \( f(4)=4f(1)=f(2) \). If \( f(4)\neq 0 \) we get \[ f(2)^2+f(2)^2+f(4)^2=2f(2)^2+4f(2)f(4)\] hence \( f(4)=4f(2) \). We already have that \( f(4)=f(2) \) and this implies that \( f(2)=0 \), which is impossible according to our assumption. Therefore \( f(4)=0 \) and the function \( f \) has period \( 4 \). Then \( f(4k)=0 \), \( f(4k+1)=f(4k+3)=c \), and \( f(4k+2)=4c \). It is easy to verify that this function satisfies the requirements of the problem.

The remaining case is \( f(n)=n^2f(1) \) for all \( n\in\mathbb N \), or \( f(n)=cn^2 \) for some \( c\in\mathbb Z \). This function satisfies the given condition.

Thus the solutions are: \( f(x)=cx^2 \) for some \( c\in\mathbb Z \); \( f(x)=\left\{\begin{array}{rl}0,& 2\mid n,\\ c, & 2\not\mid n\end{array}\right. \) for some \( c\in\mathbb Z \); and \( f(x)=\left\{\begin{array}{rl}0,& 4\mid n,\\ c, & 2\nmid n,\\ 4c, & n\equiv 2 \mbox{ (mod } 4)\end{array}\right. \) for some \( c\in\mathbb Z \).

Given a triangle \( ABC \), assume that \( \angle C=90^{\circ} \). Let \( D \) be the foot of the perpendicular from \( C \) to \( AB \), and let \( X \) be any point of the segment \( CD \). Let \( K \) and \( L \) be the points on the segments \( AX \) and \( BX \) such that \( BK=BC \) and \( AL=AC \), respectively. Let \( M \) be the intersection of \( AL \) and \( BK \).

Prove that \( MK=ML \).

Since \( AL^2=AC^2=AD\cdot AB \) the triangles \( ALD \) and \( ABL \) are similar hence \( \angle ALD=\angle XBA \). Let \( R \) be the point on the extension of \( DC \) over point \( C \) such that \( DX\cdot DR=BD\cdot AD \). Since \( \angle BDX=\angle RDA=90^{\circ} \) we conclude \( \triangle RAD\sim\triangle BXD \) hence \( \angle XBD=\angle ARD \), therefore \( \angle ALD=\angle ARD \) and the points \( R \), \( A \), \( D \), and \( L \) belong to a circle. This implies that \( \angle RLA=90^{\circ} \) hence \( RL^2=AR^2-AL^2=AR^2-AC^2 \). Analogously we prove that \( RK^2=BR^2-BC^2 \) and \( \angle RKB=90^{\circ} \). Since \( RC\perp AB \) we have \( AR^2-AC^2=BR^2-BC^2 \), therefore \( RL^2=RK^2 \) hence \( RL=RK \). Together with \( \angle RLM=\angle RKM=90^{\circ} \) we conclude \( \triangle RLM\cong \triangle LKM \) hence \( MK=ML \).

Find all positive integers \( n \) for which there exist non-negative integers \( a_1 \), \( a_2 \), \( \dots \), \( a_n \) such that \[ \frac1{2^{a_1}}+\frac1{2^{a_2}}+\cdots+\frac1{2^{a_n}}=\frac1{3^{a_1}}+\frac2{3^{a_2}}+\cdots+\frac{n}{3^{a_n}}=1.\]

Let \( M=\max\{a_1,\dots, a_n\} \). Then we have \( 3^M=1\cdot 3^{M-a_1}+ 2\cdot 3^{M-a_2}+\cdots + n\cdot 3^{M-a_n}\equiv 1+2+\cdots+n=\frac{n(n+1)}2 \) (mod \( n \)). Therefore, the number \( \frac{n(n+1)}2 \) must be odd and hence \( n\equiv 1 \) (mod 4) or \( n\equiv 2 \) (mod 4).

We will now prove that each \( n\in\mathbb N \) of the form \( 4k+1 \) or \( 4k+2 \) (for some \( k\in\mathbb N \)) there exist integers \( a_1 \), \( \dots \), \( a_n \) with the described property.

For a sequence \( \mathbf a=\left(a_1, a_2, \dots, a_n\right) \) let us introduce the following notation: \[ L(\mathbf a)=\frac1{2^{a_1}}+\frac1{2^{a_2}}+\cdots+\frac1{2^{a_n}}\quad\quad\quad\mbox{ and }\quad\quad\quad R(\mathbf a)=\frac1{3^{a_1}}+\frac2{3^{a_2}}+\cdots+\frac{n}{3^{a_n}}.\] Assume that for \( n=2m+1 \) there exists a sequence \( \mathbf a=(a_1, \dots, a_n) \) of non-negative integers with \( L(\mathbf a)=R(\mathbf a)=1 \). Consider the sequence \( \mathbf a^{\prime}=(a_1^{\prime},\dots, a_{n+1}^{\prime}) \) defined in the following way: \[ a_j^{\prime}=\left\{\begin{array}{rl} a_j,& \mbox{ if } j\not \in \{m+1,2m+2\}\\ a_{m+1}+1,& \mbox{ if } j\in \{m+1,2m+2\}.\end{array}\right.\] Then we have \[ L\left(\mathbf a^{\prime}\right)=L(\mathbf a)-\frac1{2^{a_{m+1}}}+2\cdot \frac1{2^{a_{m+1}+1}}=1\;\;\;\mbox{ and }\;\;\; R\left(\mathbf a^{\prime}\right)=R(\mathbf a)- \frac{m+1}{3^{a_{m+1}}}+\frac{m+1}{3^{a_{m+1}+1}}+\frac{2m+2}{3^{a_{m+1}+1}}=1.\] This implies that if the statement holds for \( 2m+1 \), then it holds for \( 2m+2 \).

Assume now that the statement holds for \( n=4m+2 \) for some \( m\geq 2 \), and assume that \( \mathbf a=\left(a_1, \dots, a_{4m+2}\right) \) is the corresponding sequence of \( n \) non-negative integers. We will construct a following sequence \( \mathbf a^{\prime}=\left(a_1^{\prime}, a_2^{\prime}, \dots, a^{\prime}_{4m+13}\right) \) that satisfies \( L\left(\mathbf a^{\prime}\right)=R\left(\mathbf a^{\prime}\right)=1 \) thus proving that the statement holds for \( 4m+13 \). Define: \[ a^{\prime}_j=\left\{ \begin{array}{rl} a_{m+2}+2, &\mbox{ if } j=m+2\\ a_{j}+1, &\mbox{ if } j\in\{2m+2, 2m+3, 2m+4, 2m+5,2m+6\}\\ a_{\frac{j}2}+1, &\mbox{ if } j\in\{4m+4, 4m+6, 4m+8, 4m+10,4m+12\}\\ a_{m+2}+3, &\mbox{ if } j\in\{4m+3, 4m+5, 4m+7, 4m+9, 4m+11, 4m+13\}\\ a_j, &\mbox{ otherwise.} \end{array}\right.\]

We now have \[ L\left(\mathbf a^{\prime}\right)=L(\mathbf a)-\frac1{2^{a_{m+2}}}- \sum_{j=2}^6 \frac1{2^{a_{2m+j}}}+\frac1{2^{a_{m+2}+2}}+\sum_{j=2}^6\frac1{2^{a_{2m+j}+1}}+\sum_{j=2}^6 \frac1{2^{a_{2m+j}+1}}+6\cdot \frac1{2^{a_{m+2}+3}}=1.\] It remains to verify that \( R\left(\mathbf a^{\prime}\right)=R(\mathbf a)=1 \). We write \[ R\left(\mathbf a^{\prime}\right)-R(\mathbf a)=R\left( \begin{array}{ccccccc}a^{\prime}_{m+2}, &a^{\prime}_{4m+3}, &a^{\prime}_{4m+5}, &a^{\prime}_{4m+7}, &a^{\prime}_{4m+9}, &a^{\prime}_{4m+11}, &a^{\prime}_{4m+13}\\ m+2, & 4m+3,& 4m+5,& 4m+7,& 4m+9,& 4m+11,& 4m+13\end{array}\right)-R\left(\begin{array}{c}a_{m+2}\\ m+2\end{array}\right)\] \[ + \sum_{j=2}^6 \left( R\left(\begin{array}{cc}a^{\prime}_{2m+j}, &a^{\prime}_{4m+2j}\\ 2m+j,& 4m+j\end{array}\right)-R\left(\begin{array}{c}a_{2m+j}\\ 2m+j\end{array}\right)\right),\] where \[ R\left(\begin{array}{ccc} c_1, &\dots, &c_k\\ d_1, &\dots, &d_k\end{array}\right)=\frac{d_1}{3^{c_1}}+\cdots+\frac{d_k}{3^{c_k}}.\] For each \( j\in\{2,3,4,5,6\} \) we have \[ R\left(\begin{array}{cc}a^{\prime}_{2m+j}, &a^{\prime}_{4m+2j}\\ 2m+j,& 4m+j\end{array}\right)-R\left(\begin{array}{c}a_{2m+j}\\ 2m+j\end{array}\right)= \frac{2m+j}{3^{a_{2m+j}+1}}+ \frac{4m+2j}{3^{a_{2m+j}+1}}-\frac{2m+j}{3^{a_{2m+j}}}=0.\] The first term in the expression for \( R\left(\mathbf a^{\prime}\right)-R(\mathbf a) \) is also equal to \( 0 \) because \[ R\left( \begin{array}{ccccccc}a^{\prime}_{m+2}, &a^{\prime}_{4m+3}, &a^{\prime}_{4m+5}, &a^{\prime}_{4m+7}, &a^{\prime}_{4m+9}, &a^{\prime}_{4m+11}, &a^{\prime}_{4m+13}\\ m+2, & 4m+3,& 4m+5,& 4m+7,& 4m+9,& 4m+11,& 4m+13\end{array}\right)-R\left(\begin{array}{c}a_{m+2}\\ m+2\end{array}\right)=\] \[ =\frac{m+2}{3^{a_{m+2}+2}}+\sum_{j=1}^6 \frac{4m+2j+1}{3^{a_{m+2}+3}}-\frac{m+2}{3^{a_{m+2}}}=0.\] Thus \( R\left(\mathbf a^{\prime}\right)=0 \) and the statement holds for \( 4m+13 \). It remains to verify that there are sequences of lengths \( 1 \), \( 5 \), \( 9 \), \( 13 \), and \( 17 \). One way to choose these sequences is: \[ (1), \;\;\; (2,1,3,4,4), \;\;\; (2,3,3,3,3,4,4,4,4),\;\;\; (2,3,3,4,4,4,5,4,4,5,4,5,5),\] \[ (3,2,2,4,4,5,5,6,5,6,6,6,6,6,6,6,5).\]