## The 54th International Mathematical Olympiad: Problems and Solutions## Day 1 (July 23th, 2013) Problem 1 Assume that \( k \) and \( n \) are two positive integers. Prove that there exist positive integers \( m_1 \), \( \dots \), \( m_k \) such that \[ 1+\frac{2^k-1}{n}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_k}\right).\] We will prove the statement using induction on \( k \). More precisely, we will prove the following: For \( k=1 \), we can take \( m_1=n \), and the required equality is trivial. Assume now that statement holds for a positive integer \( k \). We want to prove that for every integer \( n \) there exists positive integers \( m_1 \), \( \dots \), \( m_{k+1} \) that satisfy \[ 1+\frac{2^{k+1}-1}{n}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_{k+1}}\right).\] We will distinguish the cases of odd and even \( n \). **Case 1.**\( n \) is odd. Then \( \frac{n+1}2\in\mathbb N \) and according to inductional hypothesis there are integers \( m_1 \), \( \dots \), \( m_k \) such that \[ 1+\frac{2^k-1}{\frac{n+1}2}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_k}\right).\] By taking \( m_{k+1}=n \) we obtain: \begin{eqnarray*} \left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_{k+1}}\right)&=&\left(1+\frac{2^k-1}{\frac{n+1}2}\right)\cdot \left(1+\frac1n\right) = \left(1+\frac{2^{k+1}-2}{n+1}\right)\cdot\frac{n+1}n=\frac{n+1+2^{k+1}-2}n=1+\frac{2^{k+1}-1}n. \end{eqnarray*}**Case 2.**\( n \) is even. Then \( \frac{n}2\in\mathbb N \) and according to inductional hypothesis there are integers \( m_1 \), \( \dots \), \( m_k \) such that \[ 1+\frac{2^k-1}{\frac{n}2}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_k}\right).\] By taking \( m_{k+1}=2^{k+1}+n-2 \) we obtain: \begin{eqnarray*} \left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_{k+1}}\right)&=&\left(1+\frac{2^k-1}{\frac{n}2}\right)\cdot \left(1+\frac1{2^{k+1}+n-2}\right) = \left(1+\frac{2^{k+1}-2}{n}\right)\cdot \left(1+\frac1{2^{k+1}+n-2}\right) \\ &=&\frac{2^{k+1}+n-2}n\cdot\frac{2^{k+1}+n-2+1}{2^{k+1}+n-2}=1+\frac{2^{k+1}-1}n. \end{eqnarray*}
Problem 2
Given \( 2013 \) red and \( 2014 \) blue points in the plane, assume that no three of the given points lie on a line.
A partition of the plane is called We will prove that \( 2013 \) is the smallest value for \( k \) for which one can guarantee the perfect partition. We will first show that there is a configuration of points for which \( 2013 \) lines are necessary to achieve the perfect partition. Consider the regular \( 4027 \)-gon \( A_1A_2\cdots A_{4027} \) inscribed in the unit circle. Assume that the vertices \( A_{2k+1} \) are red for \( k\in\{0,1,\dots, 2013\} \) and that the other vertices are blue. For each \( j\in\{1,2,\dots, 4026\} \) the shorter arc \( A_jA_{j+1} \) has to intersect one of the lines of the partition. Hence there are \( 4026 \) points of intersections of the unit circle with the lines of the partition. Since each line can contain at most \( 2 \) of the points, we must have at least \( 2013 \) lines in the partition. We will now prove that it is always possible to form a perfect partition using \( 2013 \) lines. Assume that there are \( 2013 \) red and \( 2014 \) blue points. Let \( W_1\dots W_k \) be the convex hull of these points. If any point of this convex hull is red, say \( W_1 \), then there is a line \( m \) that separates the plane into two regions one of which contains \( W_1 \) only. Let \( \{R_1,\dots, R_{2012}\} \) be the set of red points other than \( W_1 \). For each \( j\in\{1,2,\dots, 1006\} \) we consider the line \( R_{2j-1}R_{2j} \). There are two lines \( l_j \) and \( l_j^{\prime} \) parallel to \( R_{2j-1}R_{2j} \) such that the region between \( l_j \) and \( l_j^{\prime} \) does not contain any points other than \( R_{2j-1} \) and \( R_{2j} \). The lines \( m \), \( l_1 \), \( l_1 \), \( l_2 \), \( l_2^{\prime} \), \( \dots \), \( l_{1006} \), \( l_{1006}^{\prime} \) generate a perfect partition. If all of the points \( W_1 \), \( \dots \), \( W_k \) are blue, then there is a line \( p \) parallel to \( W_1W_2 \) that separates the plane into two regions: one containing only the points \( W_1 \) and \( W_2 \). Let us denote by \( B_1 \), \( \dots \), \( B_{2012} \) the remaining blue points. For each \( j\in\{1,2,\dots, 1006\} \) we consider the line \( B_{2j-1}B_{2j} \). There are two lines \( l_j \) and \( l_j^{\prime} \) parallel to \( B_{2j-1}B_{2j} \) such that the region between \( l_j \) and \( l_j^{\prime} \) does not contain any points other than \( B_{2j-1} \) and \( B_{2j} \). The lines \( p \), \( l_1 \), \( l_1 \), \( l_2 \), \( l_2^{\prime} \), \( \dots \), \( l_{1006} \), \( l_{1006}^{\prime} \) generate a perfect partition. Problem 3 Let \( A_1 \), \( B_1 \), and \( C_1 \) be the points at which the excircles touch the sides \( BC \), \( CA \), and \( AB \) of the triangle \( ABC \). Prove that if the circumcenter of \( \triangle A_1B_1C_1 \) belongs to the circumcircle of \( \triangle ABC \), then one of the angles of \( \triangle ABC \) is \( 90^{\circ} \). Denote by \( a \), \( b \), and \( c \) the lengths of the sides \( BC \), \( CA \), and \( AB \). Let \( s=\frac{a+b+c}2 \). Denote by \( A_2 \), \( B_2 \), and \( C_2 \) the points of tangency of the incircle with the sides \( BC \), \( CA \), and \( AB \). Let \( k_A \), \( k_B \), and \( k_C \) be the excircles corresponding to \( A \), \( B \), and \( C \), and let \( S_A \), \( S_B \), and \( S_C \) be their centers, respectively. Then we have \[ AC_2=AB_2=BC_1=CB_1=s-a,\quad\quad BA_2=BC_2=CA_1=AC_1=s-b,\quad\quad CA_2=CB_2=BA_1=AB_1=s-c. \] Since the circumcenter of \( \triangle A_1B_1C_1 \) belongs to the circumcircle of \( \triangle ABC \), one of the angles of \( \triangle A_1B_1C_1 \) has to be obtuse. Assume that \( \angle B_1A_1C_1> 90^{\circ} \). Then the circumcenter of \( \triangle A_1B_1C_1 \) and the point \( A \) belong to the same arc \( BC \) of the circumcircle of \( \triangle ABC \). Let \( M \) be the midpoint of the arc \( BC \) that contains \( A \). From \( MB=MC \), \( \angle MBA=\angle MCA \), and \( BC_1=CB_1 \) we conclude that \( \triangle MBC_1\cong \triangle MCB_1 \) and \( MB_1=MC_1 \). Therefore, \( M \) is the circumcenter of \( \triangle A_1B_1C_1 \). Since \( BA_2=CA_1 \), we conclude that \( MA_2=MA_1 \) and consequently that \( A_2 \) belongs to the circumcircle of \( \triangle A_1B_1C_1 \). Let \( B_c \) be the point of tangency of \( AB \) with the circle \( k_B \). By a well-known result from geometry, the midpoint \( M \) of the arc \( BC \) is the midpoint of \( S_CS_B \). Therefore \( S_CC_1\|S_BB_c \) and we can conclude that \( M \) belongs to the bisector of the segment \( C_1B_c \). This implies that \( B_c \) belongs to the circumcircle of \( \triangle A_1B_1C_1 \). We now use the power of the point \( B \) with respect to the circumcircle of \( \triangle A_1B_1C_1 \). We have \( BA_2\cdot BA_1=BC_1\cdot BB_c \). Since \( BB_c=s \), \( BC_1=s-a \), \( BA_2=s-b \) and \( BA_1=s-c \) we conclude \( s(s-a)=(s-b)(s-c) \) which is equivalent to \( a^2=b^2+c^2 \). According to Pythagoras’ theorem this implies that \( \angle CAB=90^{\circ} \). ## Day 2 (July 24th, 2013) Problem 4 Let \( ABC \) be an acute triangle with orthocenter \( H \), and let \( W \) be a point on the side \( BC \) between \( B \) and \( C \). The points \( M \) and \( N \) are the feet of perpendiculars from \( B \) and \( C \), respectively. Let \( \omega_1 \) be the circumcircle of \( \triangle BWN \), and let \( X \) be the point such that \( WX \) is a diameter of \( \omega_1 \). Let \( \omega_2 \) be the circumcircle of \( \triangle CWM \), and let \( Y \) be the point such that \( WY \) is a diameter of \( \omega_2 \). Prove that the points \( X \), \( Y \), and \( H \) are collinear. Let \( Z \) be the other point of intersection of \( \omega_1 \) and \( \omega_2 \). We will prove that \( X \), \( Z \), and \( H \) are collinear. In the same way we obtain that \( Y \), \( Z \), and \( H \) are collinear. From \( \angle NZW=180^{\circ}-\angle ABC \) and \( \angle MZW=180^{\circ}-\angle ACB \) we conclude that \( \angle NZM=180^{\circ}-\angle BAC \) which means that \( Z \) belongs to the circumcircle of \( \triangle NMA \). Therefore \( \angle AZN=\angle AMN \), and since \( BCMN \) is cyclic we have \( \angle AMN=\angle ABC \). Thus \( \angle AZN+\angle NZW=180^{\circ} \) and the points \( A \), \( Z \), and \( W \) lie on a line. Let \( P \) be the foot of perpendicular from \( A \) to \( BC \). Then \( BEHN \) is cyclic hence \( AH\cdot AE=AN\cdot AB \). We also have \( AZ\cdot AW=AN\cdot AB=AH\cdot AP \), therefore \( EWZH \) is cyclic and \( \angle HZW=\angle HEW=90^{\circ} \), thus the line \( ZH \) intersects \( \omega_1 \) at \( X \). In a similar way we obtain that \( Y \), \( Z \), and \( H \) are collinear, and the statement is proved. Problem 5 Let \( \mathbb Q_+ \) be the set of all positive rational numbers. Let \( f:\mathbb Q_+\to\mathbb R \) be a function that satisfies the following three conditions: **(i)**\( f(x)f(y)\geq f(xy) \) for all \( x,y\in\mathbb Q_+ \),**(ii)**\( f(x+y)\geq f(x)+f(y) \) for all \( x,y\in\mathbb Q_+ \),**(iii)**There exists a rational number \( a> 1 \) such that \( f(a)=a \).
Prove that \( f(x)=x \) for all \( x\in\mathbb Q_+ \). From \( a=f(a)=f(a\cdot 1)\leq f(a)\cdot f(1)=a\cdot f(1) \) we conclude that \( f(1)\geq 1 \). For any positive integer \( n \) we have \( f(n)=f(1+n-1)\geq f(1)+f(n-1)\geq 1+f(n-1) \), and an argument with induction implies that \( f(n)\geq n \) for all \( n\in\mathbb N \). If \( m,n\in\mathbb N \) we have \( m\leq f(m)\leq f\left(\frac mn\right)\cdot f(n) \) which implies that \( f\left(\frac mn\right)> 0 \). Therefore, the codomain of \( f \) is \( \mathbb Q_+ \) and the condition (iii) implies that \( f \) is increasing. Since \( f(a)=a \) we have \( a^2=f(a)\cdot f(a)\geq f(a^2) \) and the principle of mathematical induction implies that for each \( k\in\mathbb N \) we have \( f(a^k)\leq a^k \). Clearly, \( f(na)\geq nf(a)=na \). Assume that for some \( l\in\mathbb N \) we have \( f(la)-la=\alpha> 0 \). If \( N \) is any integer greater that \( \frac a{\alpha} \) we conclude that \( f(Nla)\geq Nf(la)\geq Nla+N\alpha> Nla+a \). There exists \( k\in\mathbb N \) such that \( \lfloor a^k\rfloor> Nl \). The condition (ii) implies: \begin{eqnarray*}a^{k+1}&\geq &f\left(a^{k+1}a\right)\geq f\left(\lfloor a^{k}\rfloor a\right)\geq f\left(\left(\lfloor a^k\rfloor -Nl\right)a\right)+f\left(Nla\right)\\ &>& \left(\lfloor a^k\rfloor -Nl\right)a+ Nla+a = \lfloor a^k\rfloor a+a.\end{eqnarray*} This is a contradiction, hence \( f(la)=la \) for all \( l\in\mathbb N \). There are integers \( p \) and \( q \) such that \( a=\frac pq \). Hence \( f(d\frac pq)=d\frac pq \) for all \( d\in\mathbb N \) and setting \( d=kq \) gives us \( f(kp)=kp \) for all \( k\in\mathbb N \). From the second equation we have \( kp=f(kp)\geq f(k)+(p-1)f(k)\geq 2f(k)+(p-2)f(k)\geq \cdots\geq pf(k) \) hence \( f(k)\leq k \). Together with already established inequality \( f(k)\geq k \) we conclude that \( f(k)=k \) for all \( k\in\mathbb N \). Assume that If for some \( x\in\mathbb Q_+ \) there exists \( \beta> 0 \) such that \( f(x)-x=\beta \). Let \( N \) be an integer such that \( Nx\in\mathbb N \). Then we have \( Nx=f(Nx)\geq Nf(x)=N(x+\beta)=Nx+N\beta \). This is a contradiction. Thus \( f(x)=x \) for all \( x\in\mathbb Q_+ \). Problem 6
Given an integer \( n\geq 3 \), assume that \( n+1 \) equally spaced points are marked on a circle. Consider all labelings of these points with the numbers \( 0 \), \( 1 \), \( \dots \), \( n \) such that each label is used exactly once. Two labelings are considered the same if one can be obtained from the other by a rotation of the circle. A labeling is Let \( M \) be the number of beautiful labelings and let \( N \) be the number of ordered pairs \( (x,y) \) of positive integers such that \( x+y\leq n \) and \( \mbox{gcd }(x,y)=1 \). Prove that \( M=N+1 \).
Assume that \( a \) and \( b \) are distinct elements of \( \{1,2,\dots, n\} \). A beautiful labeling will be called \( (a,b) \)- Notice that an \( (a,b) \)-labeling does not exist if \( a+b\leq n \), since the chords \( [0,a+b] \) and \( [a,b] \) would intersect in that case. Assume that \( a+b> n \). Assume that \( R \) is one \( (a,b) \)-labeling. For given \( c\in\{1,2,\dots, n\} \) let us define the sequence \( (z^c_k)_{k\geq 0} \) in the following way: \( z^c_0=c \), and for \( k\geq 0 \): \begin{eqnarray*} z^c_{k+1}&=&\left\{\begin{array}{ll} z^c_k+a& \mbox{if } z^c_k\leq n-a,\\ z^c_k-b&\mbox{if }z^c_k>n-a\mbox{ and }z^c_k\geq b,\\ z^c_k+a-b&\mbox{otherwise.} \end{array}\right. \end{eqnarray*} Notice that for each \( k\geq1 \) at least one of the following three equalities hold: \begin{eqnarray*} z^c_{k+1}+0&=&z^c_k+a\\ z^c_{k+1}+b&=&z^c_k+0\\ z^c_{k+1}+b&=&z^c_k+a. \end{eqnarray*} Therefore, the ordering of the labels on the circle must be \( b,0,a,z^c_k,z^c_{k+1} \). This means that the numbers \( b \), \( 0 \), \( a \), \( z^c_1 \), \( \dots \), \( z^c_m \) must appear in that order on the circle. If \( \mbox{gcd }(a,b)> 1 \), then the sequence \( (z^1_k)_{k\geq 0} \) will not contain the term \( 0 \). This contradicts the fact that the sequence has finitely many elements. We have concluded that if \( (a,b) \)-labeling exists, then \( \mbox{gcd }(a,b)=1 \). Let us now prove that if \( \mbox{gcd }(a,b)=1 \), then \( (a,b) \)-labeling must be unique. Consider the sequence \( (z_k^0)_{k\geq 0} \). Notice that we always have \( z_{k+1}\equiv z_k+a \) (mod \( a+b \)), or \( z_{k+1}\equiv z_k+2a \) (mod \( a+b \)). Therefore the sequence \( (z_k^0)_{k\geq 0} \) is obtained when the numbers greater than \( n \) are removed from the sequence of residues of \( a \), \( 2a \), \( \dots \) modulo \( a+b \). Thus \( z^0_1 \), \( \dots \), \( z^0_n \) is a uniquely determined permutation of \( \{1,2,\dots, n\} \), proving the uniqueness of the labeling Let \( L_n \) be the number of pairs \( (a,b)\in\{1,2,\dots, n\}^2 \) such that \( \mbox{gcd }(a,b)=1 \) and \( a+b> n \). We have that \( M=L_n \). It remains to prove that \( L_n=N_n+1 \), where \( N_n \) is the number of pairs \( (a,b)\in\{1,2,\dots, n\}^2 \) such that \( \mbox{gcd }(a,b)=1 \) and \( a+b\leq n \). Consider the matrix \( (D_{i,j})_{i,j\geq 1} \) such that \[ D_{i,j}=\left\{\begin{array}{ll}1&\mbox{if gcd }(i,j)=1,\\ 0&\mbox{otherwise.}\end{array}\right.\] We will use the induction to prove that \( L_n-N_n=1 \). The statement clearly holds for \( n=3 \). The number \( N_n \) represents the number ones in the matrix \( D_{i,j} \) that lie on and above the diagonal \( i+j=n \). The number \( L_n \) represents the number of ones in the matrix \( D_{i,j} \) that lie below the diagonal \( i+j=n \) and for which \( i\leq n \) and \( j\leq n \). We need to show that \( (L_{n+1}-N_{n+1})-(L_n-N_n)=0 \). Let us denote by \( G_{n+1} \) the number of ones on in the \( n+1 \)-st column that are on or above the \( n+1 \)-st row. Let \( H_{n+1} \) be the number of ones on the diagonal \( i+j=n+1 \). Then we have \( (L_{n+1}-N_{n+1})-(L_n-N_n)=2G_{n+1}-2H_{n+1} \) since the new difference \( L_{n+1}-N_{n+1} \) will gain all the ones in the \( n+1 \)-st row and \( n+1 \)-st column but loose all the ones on the diagonal. It remains to notice that \( G_{n+1}=H_{n+1}=\varphi(n+1) \), where \( \varphi(x) \) is the number of integers smaller than \( x \) and relatively prime to \( x \). |

2005-2017 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us |