## The 55th International Mathematical Olympiad: Problems and Solutions## Day 1 (July 8th, 2014) Problem 1 Let \( a_0< a_1< a_2< \cdots \) be an infinite sequence of positive integers. Prove that there exists a unique integer \( n\geq 1 \) such that \[ a_n< \frac{a_0+a_1+\cdots+a_n}n\leq a_{n+1}.\]
For \( k\geq 1 \) we will say that the term \( a_k \) is This contradiction proves that there is at least one \( n \) for which \( a_n \) is large. Let us assume that there are two positive integers \( n \) and \( m \) such that \( 1\leq n< m \) for which the given two inequalities are satisfied. Then we have \begin{eqnarray*} a_m&<& \frac{\left(a_0+\cdots+a_n\right)+\left(a_{n+1}+\cdots+a_m\right)}{m}\leq \frac{na_{n+1}+\left(a_{n+1}+\cdots+a_m\right)}{m}\\ &<& \frac{na_{m}+\left(a_{m}+\cdots+a_m\right)}{m}=a_m. \end{eqnarray*} This completes the proof of the required statement. Problem 2
Let \( n\geq 2 \) be an integer. Consider an \( n\times n \) chessboard consisting of \( n^2 \) unit squares. A configuration of \( n \) rooks on this board is We will prove that the maximal such \( k \) is equal to \( \lfloor \sqrt n-1\rfloor \). For a given board \( A \) and given \( k \), denote by \( \hat A_{i,j}(k) \) the \( k\times k \) square whose top-left corner is \( (i,j) \) (we use the usual matrix notation here). Assume that \( k\leq \lfloor \sqrt {n-1}\rfloor \). Consider a peaceful configuration of \( n \) rooks in the \( n\times n \) board \( A \), and assume that the rook in the first column belongs to the \( r \)-th row. Let us denote by \( s \) an integer such that \( s+k-1\leq n \) and \( r\in\{s, s+1, \dots, s+k-1\} \). Consider now the disjoint squares \( \hat A_{2,s}(k) \), \( \hat A_{k+2,s}(k) \), \( \hat A_{2k+2,s}(k) \), \( \dots \), \( \hat A_{(k-1)k+2,s}(k) \) each of which is completely contained in the square \( A \). There are \( k \) of them hence each of the rows \( s \), \( s+1 \), \( \dots \), \( s+k-1 \) must contain a rook in one of these squares. The cell \( (1,r) \) already contains a rook, which contradicts the assumption that the configuration is peaceful. We will now prove that for \( k= \lfloor \sqrt{ n-1}\rfloor \) there is a configuration of rooks such that each \( k\times k \) square contains a rook. Assume first that \( n=m^2 \) for some \( m\in\mathbb N \). Consider the following configuration \( C \) of rooks: for each pair \( (i,j)\in\{1,2,\dots, m\}^2 \) we place a rook in the cell \( A_{(i-1)m+j,(j-1)m+i} \). Assume that \( (i,j) \) and \( (i^{\prime},j^{\prime}) \) are two pairs of integers from \( \{1,2,\dots, m\}^2 \) such that \( (i-1)m+j=(i^{\prime}-1)m+j^{\prime} \). Since \( j,j^{\prime}\in\{1,2,\dots, m\} \) we conclude that \( j=j^{\prime} \). This implies that \( i=i^{\prime} \) and we have proved that no two rooks are in the same row. Similarly we prove that no two rooks are in the same column, and the configuration of rooks is peaceful. Assume that \( p,q\in\{1,\dots, n-m+1\}^2 \). We will prove that \( \hat A_{p,q}(m) \) contains at least one rook from the configuration \( C \). First, in order for \( \hat A_{p,q}(m) \) to be within the board we must have \( p, q\leq m^2-m+1 \). There are pairs of integers \( (a,b), (c,d)\in\{0,1,\dots, m-1\}\times\{1,2,\dots, m\} \) such that \( p=am+b \) and \( q=cm+d \). We know that a rook is located on each of the squares in the set \begin{eqnarray*}S&=&\left\{(am+c+1,cm+a+1), \left((a+1)m+c+1, cm+a+2\right), \right.\\ &&\left.\left(am+c+2,(c+1)m+a+1\right), \left((a+1)m+c+2, (c+1)m+a+2\right)\right\}.\end{eqnarray*} We will prove that there exist \( (x,y)\in\{0,1,\dots, m-1\}^2 \) such that \( (p+x,q+y)\in S \). We will form a set \( T \) of ordered pairs obtained by subtracting \( (p,q) \) from each element of \( S \). \begin{eqnarray*}T&=&\left\{(c+1-b,a+1-d), \left(m+c+1-b, a+2-d\right), \right.\\ &&\left.\left(c+2-b,m+a+1-d\right), \left(m+c+2-b, m+a+2-d\right)\right\}.\end{eqnarray*} We need to prove that at least one element of \( T \) belongs to \( \{0,1,\dots, m-1\}^2 \). Assume that \( c+1-b< 0 \) or \( a+1-d< 0 \). We have that \( 1-m\leq c+1-b\leq m-1 \) and \( 1-m\leq a+1-d\leq m-1 \). It suffices to prove that \( c+2-b< m \) and \( a+2-d< m \). Assume that \( c+2-b=m \). Then we would have \( c=m-1 \) and \( b=1 \) which together with \( cm+d\leq m^2-m+1 \) would imply that \( d=1 \). In this case we would have \( c+1-b\geq 0 \) and \( a+1-b\geq 0 \), which is not possible. In a similar way we prove that \( a+2-d< m \). This completes the proof of the statement for the case when \( n \) is a perfect square. If \( n \) is not a perfect square, denote by \( n^{\prime} \) the smallest perfect square larger than \( n \). Let \( k= \sqrt{n^{\prime}} \). There is a peaceful configuration of rooks on \( n^{\prime}\times n^{\prime} \) board \( A \) in which every \( k\times k \) square contains a rook. Consider a arbitrary \( n^{\prime}-n \) rooks in this configuration. For each of these rooks we remove the entire column and row of the board that contains the rook. We obtain an \( n\times n \) square with the desired properties. Problem 3 Convex quadrilateral \( ABCD \) has \( \angle ABC=\angle CDA=90^{\circ} \). Point \( H \) is the foot of the perpendicular from \( A \) to \( BD \). Points \( S \) and \( T \) lie on sides \( AB \) and \( AD \), respectively, such that \( H \) lies inside triangle \( SCT \) and \[ \angle CHS-\angle CSB=90^{\circ}, \quad\quad \angle THC-\angle DTC=90^{\circ}.\] Prove that line \( BD \) is tangent to the circumcircle of triangle \( TSH \). It suffices to prove that the circumcenter of \( \triangle TSH \) lies on \( AH \). Denote by \( O_D \) and \( OB \) the intersection of the perpendicular bisectors of \( TH \) and \( TS \) with \( HA \), respectively. We need to prove that \( O_D \) and \( O_B \) coincide. Let us denote by \( B^{\prime} \) and \( D^{\prime} \) the intersections of perpendicular bisectors of \( HS \) and \( HT \) with the lines \( AB \) and \( AD \), respectively. From the angle-bisector theorem we know that \( AO_D:O_DH=D^{\prime}A: D^{\prime}H \) and \( AO_B:O_BH=B^{\prime}A:B^{\prime}H \). Therefore it suffices to prove that \( D^{\prime}A:D^{\prime}H=B^{\prime}A:B^{\prime}H \). Assume that the line \( TD \) intersects the circumcircle of \( \triangle CHT \) at point \( Q \). Then \[ \angle TQC=180^{\circ} -\angle THC=90^{\circ}-\left(\angle THC-90^{\circ}\right)=90^{\circ}-\angle DTC.\] Therefore \( \angle QCT=90^{\circ} \) and the center of the circumcirle must belong to \( TD \). Since the center belongs to the bisector of \( TH \) we conclude that \( D^{\prime} \) is the center of the circumcircle of \( \triangle CHT \). In an analogous way we prove that \( B^{\prime} \) is circumcenter of \( \triangle CHS \). The circumcircles of \( \triangle THC \) and \( \triangle CHS \) intersect at \( C \) and \( H \), hence the line \( D^{\prime}B^{\prime} \) is the perpendicular bisector of \( CH \). From \( CH\perp B^{\prime}D^{\prime} \) and \( CB\perp BB^{\prime} \) we conclude that \( \angle HCB=\angle XB^{\prime}B \). Denote by \( X \) and \( Y \) the intersections of the perpendicular bisector of \( HA \) with the lines \( B^{\prime}D^{\prime} \) and \( HA \). Then \( X \) is the center of the circle circumscribed around \( \triangle CHA \). Hence \( \angle AXY=\frac12AXH=\angle ATH \) and \begin{eqnarray*}\angle XAD^{\prime}&=&90^{\circ}-\angle AXY-\angle D^{\prime}AH=\angle ADH-\angle AXY\\&=&\angle ACB-\angle ACH=\angle HCB=\angle XB^{\prime}B.\end{eqnarray*} Therefore \( XA \) is the tangent to the circumcircle of \( \triangle D^{\prime}AB^{\prime} \) which means that \( k(X, XA) \) is orthogonal to the circle \( l(D^{\prime}AB^{\prime}) \). Since \( X\in D^{\prime}B^{\prime} \), the circle \( k \) is an Apollonius circle of the points \( D^{\prime} \) and \( B^{\prime} \) hence \( AD^{\prime}:AB^{\prime}=HD^{\prime}:HB^{\prime} \) which implies the required statement. ## Day 2 (July 9th, 2014) Problem 4 Points \( P \) and \( Q \) lie on side \( BC \) of acute-angled triangle \( ABC \) such that \( \angle PAB=\angle BCA \) and \( \angle CAQ=\angle ABC \). Points \( M \) and \( N \) lie on lines \( AP \) and \( AQ \), respectively, such that \( P \) is the midpoint of \( AM \), and \( Q \) is the midpoint of \( AN \). Prove that lines \( BM \) and \( CN \) intersect on the circumcircle of triangle \( ABC \). Let us denote by \( R \) the intersection of \( BM \) and \( CN \). Let \( X \) be the point symmetric to \( B \) with respect to \( P \). Then \( AX\|BM \) hence \( \angle BMP=\angle XAP \). Since \( \angle BAP=\angle ACQ \) and \( \angle APB=\angle AQC=\angle BAC \) we conclude that \( \triangle BAP\sim\triangle ACQ \). Therefore \( \triangle PAX\sim\triangle QCN \) hence \( \angle QCN=\angle PAX=\angle BMP \). This means that \( R \), \( M \), \( C \), and \( P \) belong to a circle which implies that \( \angle MRC=\angle MPC=\angle BAC \). Thus \( R \) belongs to the circumcircle of \( \triangle ABC \). Problem 5 For each positive integer \( n \), the Bank of Cape Town issues coins of denominations \( \frac1n \). Given a finite collection of such coins (of not necessarily different denominations) with total value at most \( 99+\frac12 \), prove that it is possible to split this collection into \( 100 \) or fewer groups, such that each group has total value at most \( 1 \). We will use the induction on \( n \) to prove the following statement: The set of coins whose total value does not exceed \( n-\frac12 \) can be partitioned into at most \( n \) subsets each of which has a total value of at most \( 1 \). The statement is easy to verify for \( n\leq 2 \), and assume it is true for \( n-1 \). Assuming that the statement is true for all numbers smaller than \( n \), assume that it is false for \( n \), and consider the configuration with the smallest number of coins that can not be partitioned in the desired way. Denote by \( S \) the set of the coins in this configuration. We can be certain that for each \( k \) there are at most \( k-1 \) coins of value \( \frac1{k} \), as otherwise we could replace \( k \) coins with a coin of value \( 1 \). Moreover, if \( k \) is even number, there is at most one coin of value \( \frac1{k} \) since two coins of value \( \frac1k \) could be replaced by one coin of value \( \frac1{k/2} \). Let \( m \) be the largest integer for which \( \frac1m\in S \). Then the set \( S\setminus \{\frac 1m\} \) can be partitioned into at most \( n \) subsets such that the total value \( \gamma_i \) of the \( i \)-th subset is at most \( 1 \). Since the coin \( \frac1m \) cannot be added to the \( i \)th subset we must have \( 1-\frac1m< \gamma_i\leq 1 \). The total sum of coins in \( S \) is at most \( n-\frac1m \), therefore \( n-\frac12\geq \frac1m+\sum_i \gamma_i> \frac1m+\left(1-\frac1m\right)\cdot n \) which implies that \( m< 2(n-1) \). For each \( 1\leq i\leq m \) let us denote by \( f(i) \) the number of coins in \( S \) that have value \( \frac1i \). We now have \begin{eqnarray*}\sum_{c\in S} c&\leq& \sum_{i=1}^{n-1} \frac{f(2i)}{2i}+\sum_{i=1}^{n-2}\frac{f(2i+1)}{2i+1}\\\ &\leq&\frac12+ \sum_{i=2}^{n-1} \frac{1}{2i}+\sum_{i=2}^{n-1}\frac{2i}{2i+1} \leq \frac12+\sum_{i=2}^{n-1}\left(\frac1{2i}+\frac{2i}{2i+1}\right)\\&<&\frac12+ n-2=(n-1)-\frac12. \end{eqnarray*} This way we have obtained a configuration of coins of total value smaller than \( (n-1)-\frac12 \) and by induction hypothesis it can be partitioned into \( n-1 \) subsets each of which has value smaller than \( 1 \). This is a contradiction. Problem 6
A set of lines in the plane is in
Given a configuration of \( n \) lines, denote by \( x \) the maximal number of lines that can be colored in blue so that the conditions of the problem are satisfied, and denote by \( \mathcal C \) one such coloring. Let \( \mathcal N \) be the set of lines that are non-blue in the coloring \( \mathcal C \). Each intersection point of two blue lines will be called For every blue region \( B_1B_2\dots B_k \) consider the internal angles corresponding to its blue vertices and assign the value of \( \frac1{k-2} \) to each of those angles. All other angles are assigned value \( 0 \). The sum of the values of angles in each blue region is \( 1 \) implying that the sum of all labels of all angles in the coloring \( \mathcal C \) is equal to \( \beta \).
For each blue point \( B \) we calculate the sum of all labeled angles whose vertex is \( B \). If the sum of the labels is smaller than \( 2 \), we call such a point a -
**Lemma**Assume that \( X \) is a bad point. Then all four angles around \( X \) belong to blue regions. Exactly one of these blue regions is a triangle (we will denote it by \( T(X) \)) and at most two are quadrilaterals. The non-blue line that contains the edge of \( T(X) \) also contains the edge of two other blue regions whose vertex is \( X \). -
**Proof.**If none of the regions is a triangle, then all four of the angles have value of at most \( \frac12 \) hence their sum cannot be bigger than \( 2 \).Assume that \( PQX \) is a blue triangle with vertex \( X \). Let \( l \) be the non-blue line that contains \( P \) and \( Q \). Denote by \( \mathcal P \) and \( \mathcal Q \) the regions different from \( \triangle PQX \) whose edges are \( XP \) and \( XQ \). Let us denote by \( \mathcal Y \) the fourth region with vertex \( X \). The regions \( \mathcal P \) and \( \mathcal Q \) cannot be triangles because no other line passes through \( X \). Assume that \( \mathcal Y \) is a blue triangle. Assume \( Q^{\prime} \) and \( P^{\prime} \) are vertices of this triangle that belong to lines \( XP \) and \( XQ \). Since the segments \( XP \) and \( XQ^{\prime} \) cannot be intersected by any of the other lines, we conclude that \( \mathcal P \) is not blue. Similarly, \( \mathcal Q \) is not blue, and the sum of labels of angles with vertex \( X \) is exactly \( 2 \), contradicting the assumption that \( X \) is bad. Therefore, \( \triangle XPQ \) is the only blue triangle with vertex \( X \). Consequently, each region that has vertex \( X \) must be a blue region (otherwise \( X \) would not be bad). Let \( l^{\prime} \) be the non-blue line that contains the edge of \( \mathcal Y \) and let us denote by \( U \) and \( V \) the intersections of \( l^{\prime} \) with the lines \( XP \) and \( XQ \). Since \( \mathcal Q \) is blue, the segment \( XU \) is intersected by a blue line. Similarly, the segment \( XV \) is intersected by another blue line, and \( \mathcal Y \) cannot be a quadrilateral.
A consequence of the previous lemma is that the sum of all labels of angles with vertex at any blue point is at most \( \frac73 \). Let \( B \) be the number of bad points and \( G \) the number of good points. Then we have \( \beta\leq 2G+\frac73 B \). For \( l\in\mathcal N \) denote by \( \beta(l) \) the number of blue regions with an edge on \( l \) and by \( \mathcal P_l \) the set of bad points that are vertices of blue triangles with edges on \( l \). Fix a line \( l \) for which \( \mathcal P_l=\left\{X_1, \dots, X_m\right\}\neq\emptyset \). Assume that \( P_1 \), \( Q_1 \), \( P_2 \), \( Q_2 \), \( \dots \), \( P_m \), \( Q_m \) are points on \( l \) in that order such that \( T(X_i)=\triangle X_iP_iQ_i \) for each \( 1\leq i\leq m \). According to the lemma we know that for each \( i \) there exist two non-triangular blue regions \( \mathcal P_i \) and \( \mathcal Q_i \) whose one edge is on \( l \) such that \( X_iP_i \) is an edge of \( \mathcal P_i \) and \( X_iQ_i \) is an edge of \( Q_i \). Since all \( \mathcal P_i \) are distinct we conclude that \( \beta(l)\geq 2m \). Let us denote \( \mathcal B=\left\{l\in\mathcal N: \mathcal P_l\neq \emptyset\right\} \). Therefore \begin{eqnarray*} \beta&=&\sum_{l\in\mathcal N}\beta(l)=\sum_{l\in\mathcal B}\beta(l)+\sum_{l\in\mathcal N\setminus \mathcal B}\beta(l) \geq \sum_{l\in\mathcal B}2\left|\mathcal P_l\right|+\left|\mathcal N\setminus \mathcal B\right|\\& \geq& \sum_{l\in\mathcal B}\left(\left|\mathcal P_l\right|+1\right)+\left|\mathcal N\setminus \mathcal B\right| =\sum_{l\in\mathcal B}\left|\mathcal P_l\right|+\left|\mathcal B\right|+\left|\mathcal N\setminus \mathcal B\right|\\ &=&B+n-x. \end{eqnarray*} We now obtain \( B+n-x\leq 2G+\frac73B \) which implies the inequality \[ n-x\leq 2G+\frac43B\leq 2(G+B)=2\binom x2.\] The consequence of the last relation is \( x\geq\sqrt n \). |

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