The 53rd International Mathematical Olympiad: Problems and Solutions

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\).

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 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 \newline 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\).

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,\newline 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,\newline 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,\newline c, & 2\nmid n,\newline 4c, & n\equiv 2 \mbox{ (mod } 4)\end{array}\right.\) for some \(c\in\mathbb Z\).

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\).

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\}\newline 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\newline a_{j}+1, &\mbox{ if } j\in\{2m+2, 2m+3, 2m+4, 2m+5,2m+6\}\newline a_{\frac{j}2}+1, &\mbox{ if } j\in\{4m+4, 4m+6, 4m+8, 4m+10,4m+12\}\newline a_{m+2}+3, &\mbox{ if } j\in\{4m+3, 4m+5, 4m+7, 4m+9, 4m+11, 4m+13\}\newline 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}\newline 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}\newline m+2\end{array}\right)\] \[+ \sum_{j=2}^6 \left( R\left(\begin{array}{cc}a^{\prime}_{2m+j}, &a^{\prime}_{4m+2j}\newline 2m+j,& 4m+j\end{array}\right)-R\left(\begin{array}{c}a_{2m+j}\newline 2m+j\end{array}\right)\right),\] where \[R\left(\begin{array}{ccc} c_1, &\dots, &c_k\newline 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}\newline 2m+j,& 4m+j\end{array}\right)-R\left(\begin{array}{c}a_{2m+j}\newline 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}\newline 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}\newline 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).\]