Образователни технологии
PROBLEMS 2 AND 5 ON THE IMO’2019 PAPER
Резюме. The aim of the present note is to discuss Problem 2 and Problem 5 on the IMO’2019 paper. The \(60^{\text {th }}\) edition of the International Mathematical Olympiad (IMO) took place in the city of Bath, United Kingdom, 11 – 22 July 2019, with the participation of 621 students from 112 countries. The event is the most prestigious scientific Olympiad for high school students. Problem 2 and Problem 5 are of mean difficulty on the paper. Problem 2 was solved fully (7 points) by 98 participants, 92 students were marked with 6 points, 3 with 5 points, 6 with 4 points, 6 with 3 points, 30 with 2 points, 135 with 1 point and 251 with 0 points. The mean result of all the 621 participants in the Olympiad is 2,399. Analogously, Problem 5 was solved fully (7 points) by 250 participants, 3 students were marked with 6 points, 7 with 5 points, 5 with 4 points, 12 with 3 points, 168 with 2 points, 20 with 1 point and 156 with 0 points. The mean result of all the 621 participants is 3,567.
Ключови думи: Olympiad; problem solving; collinear points; concyclic points; parallel lines; Reim’s theorem
The IMO Problem 2 under consideration is the following:
Problem 2. In triangle \(A B C\), point \(A_{1}\) lies on side \(B C\) and point \(B_{1}\) lies on side \(A C\). Let \(P\) and \(Q\) be points on segments \(A A_{1}\) and \(B B_{1}\), respectively, such that \(P Q\) is parallel to \(A B\). Let \(P_{1}\) be a point on line \(P B_{1}\), such that \(B_{1}\) lies strictly between \(P\) and \(P_{1}\), and \(\angle P P_{1} C=\angle B A C\). Similarly, let \(Q_{1}\) be a point on line \(Q A_{1}\), such that \(A_{1}\) lies strictly be\(\angle P P_{1} C=\angle B A C\). Similarly, let \(Q_{1}\) be a point on line \(Q A_{1}\), such that \(A_{1}\) lies strictly between \(Q\) and \(Q_{1}\),and \(\angle C Q_{1} Q=\angle C B A\). Prove that points \(P, Q, P_{1}\),and \(Q_{1}\) areconcyclic.
(Proposed by Anton Trygub, Ukraine)
Solution: At the beginning we will examine several facts with self-dependent significance.
Reim’s theorem 1. Let the circles \(k_{1}\) and \(k_{2}\) intersect in points \(M\) and \(N\). If \(A\) and \(B\) are points on \(k_{1}\), while the lines \(A M\) and \(B N\) intersect \(k_{2}\) for a second time in points \(C\) and \(D\), respectively, then \(A B \| C D\).
Proof: Since the quadrilaterals \(A B N M\) and \(M N D C\) are inscribed in \(k_{1}\) and \(k_{2}\), respectively, then \(\angle A B N=180^{\circ}-\angle A M N=\angle N M C=180^{\circ}-\angle N D C\). It follows, that \(\angle A B N+\angle N D C=180^{\circ}\) and consequently \(A B \| C D\) (property of the corresponding angles).
Reim’s theorem 2. Let the quadrilateral \(A B N M\) is inscribed in the circle \(k_{1}\). If points \(C\) and \(D\) lie on the lines \(A M\) and \(B N\), respectively, in a way that \(A B \| C D\), then points \(M, N, D\) and \(C\) are concyclic.
Proof: Since the quadrilateral \(A B N M\) is inscribed, then \(\angle A B N=180^{\circ}-\angle A M N=\angle N M C\). But \(\angle A B N+\angle N D C=180^{\circ}\) (corresponding angles), because \(A B \| C D\). Consequently \(\angle N M C+\angle N D C=180^{\circ}\) and we conclude, that the quadrilateral \(M N D C\) is inscribed.
Equivalent form of Reim’s theorem 2. Given is \(\triangle A B C\) inscribed in the circle \((A B C)\). Let \(A_{1}\) be a point from the interior of the side \(B C\) and let the line \(A A_{1}\) intersects ( \(A B C\) ) for a second time in point \(D\), while \(B_{1}\) be a point from the interior of the side \(A C\) and the line \(B B_{1}\) intersects ( \(A B C\) ) for a second time in point \(E\). Let \(P\) and \(Q\) be points on the segments \(A A_{1}\) and \(B B_{1}\), respectively, in a way that \(P Q \| A B\). Then the points \(P, Q, D\) and \(E\) are concyclic.
Proof: Since the quadrilateral \(A B D E\) is inscribed, then \(\angle A B E=\angle A D E\). But \(P Q \| A B\) implies that \(\angle A B E=\angle P Q E\). Consequently, \(\angle A D E=\angle P Q E\), which is enough to claim, that the points \(P, Q, D\) and \(E\) are concyclic.
Theorem 1 and theorem 2 could be unified as a necessary and sufficient condition: Let the quadrilateral \(A B N M\) be inscribed in the circle \(k_{1}\), while points \(C\) and \(D\) lie on the lines \(A M\) and \(B N\), respectively. Lines \(A B\) and \(C D\) are parallel iff the points \(M\), \(N\), \(D\) and \(C\) are concyclic.
In various sources the last formulation is known as Reim’s theorem.
Reim’s theorem 3. Let the circles \(k_{1}\) and \(k_{2}\) intersect in points \(M\) and \(N\). If \(A\) and \(B\) are points on \(k_{1}\), while the line \(A M\) intersects \(k_{2}\) for a second time in point \(C\) and \(D\) is a point on \(k_{2}\) such, that \(A B \| C D\), then the points \(B, N\) and \(D\) are collinear.
Proof: Since the quadrilaterals \(A B N M\) and \(M N D C\) are inscribed in \(k_{1}\) and \(k_{2}\), respectively, then \(\angle A B N=180^{\circ}-\angle A M N=\angle N M C=180^{\circ}-\angle N D C\). It follows, that \(\angle A B N+\angle N D C=180^{\circ}\). But \(A B \| C D\) and the last equality is possible only in case \(B, N\) and \(D\) are collinear.
Remark. In applications Reim’s theorems are used as sufficient conditions for parallelism, collinearity or to prove that four points are concyclic.
We start the solution of Problem 2.
Let \(A A_{1}\) and \(B B_{1}\) intersect for a second time the out-circle ( \(A B C\) ) of \(\triangle A B C\) in points \(D\) and \(E\), respectively. Let the lines \(P B_{1}\) and \(Q A_{1}\) intersect the side \(A B\) in points \(R\) and \(S\), respectively. It follows from the condition of the problem, that the quadrilaterals \(A R C P_{1}\) and \(S B Q_{1} C\) are inscribed in two cir cles. By the property of intersecting chords in the first one we deduce, that \(B_{1} C . B_{1} A=B_{1} P_{1} . B_{1} R\). . By the same property with respect to the out-circle ( \(A B C\) ) we deduce, that \(B_{1} C \cdot B_{1} A=B_{1} B \cdot B_{1} E\) and consequently \(B_{1} P_{1} \cdot B_{1} R=B_{1} B \cdot B_{1} E\). Since \(\triangle B_{1} P Q \sim \triangle B_{1} R B\), then \(\cfrac{B_{1} B}{B_{1} Q}=\cfrac{B_{1} R}{B_{1} P}\), from where \(B_{1} B \cdot B_{1} P=B_{1} Q \cdot B_{1} R\). Multiply the left and the right hand sides of this equality by the above obtained \(B_{1} P_{1} \cdot B_{1} R=B_{1} B \cdot B_{1} E\).
After corresponding simplifications we come to \(B_{1} P \cdot B_{1} P_{1}=B_{1} Q \cdot B_{1} E\). But this means, that the points \(P, Q, P_{1}\) and \(E\) are concyclic, i.е. the point \(P_{1}\) lies on the circle defined by the points \(P, Q\) и \(E\).
In a similar way, by the property of the intersecting chords with respect to the out-circle \(S B Q_{1} C\) we deduce, that \(A_{1} C \cdot A_{1} B=A_{1} Q_{1} \cdot A_{1} S\), while by the same property with respect to ( \(A B C\) ) we have, that \(A_{1} C \cdot A_{1} B=A_{1} A \cdot A_{1} D\). Consequently \(A_{1} Q_{1} . A_{1} S=A_{1} A . A_{1} D\). Since \(\triangle A_{1} Q P \sim \triangle A_{1} S A\), then \(\cfrac{A_{1} A}{A_{1} P}=\cfrac{A_{1} S}{A_{1} Q}\) and therefore \(A_{1} A . A_{1} Q=A_{1} P . A_{1} S\). Multiply the left and the right hand sides of this equality by the above obtained \(A_{1} Q_{1} \cdot A_{1} S=A_{1} A \cdot A_{1} D\). . After corresponding simplification we come to \(A_{1} Q \cdot A_{1} Q_{1}=A_{1} P \cdot A_{1} D\). This means that the points \(P, Q, Q_{1}\) and \(D\) are concyclic, i.e. the point \(Q_{1}\) lies on the circle determined by the points \(P, Q\) and \(D\).
It remains to note that according to the equivalent formulation of Reim’s theorem 2 the points \(P, Q, D\) and \(E\) are concyclic. Consequently, the circle determined by the points \(P, Q\) and \(E\) coincides with the circle determined by the points \(P, Q\) and \(D\). Thus, the points \(P, Q, P_{1}\) and \(Q_{1}\) are concyclic.
The IMO Problem 5 under consideration is the following:
Problem 5. The Bank of Bath issues coins with an \(H\) on one side and a \(T\) on the other. Harry has \(n\) of these coins arranged in a line from left to right. He repeatedly performs the following operation:
if there are exactly \(k \gt 0\) coins showing \(H\), then he turns over the \(k\)-th coin from the left; otherwise, all coins show \(T\) and he stops. For example, if \(n=3\) the process starting with the configuration THT would be THT → HHT \(\rightarrow H T T \rightarrow T T T\), which stops after three operations.
(a) Show that, for each initial configuration, Harry stops after a finite number of operations.
(b) For each initial configuration \(C\), let \(L(C)\) be the number of operations before Harry stops. For example, \(L(T H T)=3\) and \(L(T T T)=0\). Determine the average value of \(L(C)\) over all \(2^{n}\) possible initial configurations \(C\).
(Proposed by David Altizio, USA)
Solution: Each execution of the operation from the condition of the problem will be called move. A coin is \(H\)-coin, if \(H\) is on the visible side of the coin. In the opposite case the coin is \(T\)-coin.
Lemma. If all coins in a configuration with length \(n\) are \(H\)-coins, then after \(n\) moves they become \(T\)-coins.
Proof: It follows from the scheme below:
HH...HH → HH...HT → HH...HTT → HH...TTT → .. → .HT...TTT → TT...TTT .
We start the solution of Problem 5.
a) The assertion will be proved by induction with respect to \(n\). It is obviously true when \(n=1\). Assume that it is true for all \(k \leq n\) for a fixed \(n\). We will prove it for \(n+1\). If the last coin in a configuration of \(n+1\) coins is a \(T\)-coin, it remains unchanged until the end (in order to be changed, we need \(n+1 H\)-coins, but such a number is not possible). The problem is reduced to the case \(n\), when the assertion is true because of the inductive assumption.
If the last coin in the configuration is \(H\)-coin, consider the most left \(T\)-coin. Let it be \(i\)-th in turn. We will show that after some moves (finite number) the \(T\)-coin in question is changed into \(H\)-coin. Consider the piece of the configuration consisted of all coins from the \((i+1)\)-th one to the right up to the \(n\)-th on-th one included. If the coins in this piece are \(T\)-coins, the number of all \(H\)-coins in the whole configuration is equal to \(i-1+1=i\) and this leads to the change of the \(T\)-coin under consideration. Now, let the piece contain a \(H\)-coin at least. Then, the number of all \(H\)-coins in the whole configuration is greater than \(i\). If it does not decrease to become equal to \(i\) and the \(T\)-coin under consideration does not change, the number will remain greater than \(i\) and will change between \(i+1\) and \(n\). This means that all moves will be executed inside the piece. Note that the dimension of the piece is less than \(n\) and the inductive assumption may be applied. Thus, all coins in the piece become \(T\)-coins, while the number of the \(H\)-coins in the whole configuration becomes equal to \(i\). We conclude that the most left \(T\)-coin under consideration becomes \(H\)-coin.
We have proved that the most left \(T\)-coin „moves” to the right after a finite number of moves and as a result, again after a finite number of moves all coins from the initial configuration will become \(H\)-coins. Now, it is enough to apply the lemma. b) Let \(N_{n}\) be the sum of the moves that lead to the end with respect to all \(2^{n}\) possible initial configurations of \(n\) coins. We will prove that
\[ \cfrac{N_{n}}{2^{n}}=\cfrac{n(n+1)}{4} \]
When \(n=1\), there are two possible configurations: \(H\) and \(T\). At the same time \(L(H)=1, L(T)=0, N_{1}=1+0=1, \cfrac{N_{1}}{2^{1}}=\cfrac{1}{2}\) and the formula is satisfied. When \(n=2\), there are four possible configurations: \(H H, H T, T H\) and \(T T\). At the same time \(L(H H)=2\), because the moves are: \(H H \rightarrow H T \rightarrow T T . L(H T)=1\), because the move is unique: \(H T \rightarrow T T . L(T H)=3\), because the moves are: \(T H \rightarrow H H \rightarrow H T \rightarrow T T\). And \(L(T T)=0\). Then, \(\cfrac{N_{2}}{2^{2}}=\cfrac{2+1+3+0}{4}=\cfrac{3}{2}\) and the formula is satisfied again.
In order to prove the formula in the general case, we will compute \(N_{n+1}\) firstly. As mentioned in а), if the last coin in the configuration of \(n+1\) coins is \(T\)-coin, it remains unchanged until the end. For this reason the sum \(N_{n+1}\) contains also the moves that bring to the end the configurations of that type, i.e. \(N_{n}\) is present in \(N_{n+1}\). In case the last coin is \(H\)-coin, we may consider the most left \(T\)-coin again. Denote by \(j\) the number of the coins, starting by the coin closed to the right of \(T\) and finishing by the \(n\)-th coin (included). We will follow what happens when \(j\) is fixed and afterwards we will sum up with respect to all possible values of \(j\). From the configuration \(H H \ldots H T . . . H\) we reach \(H H \ldots H T T . . . T H\) by \(N_{j}\) moves, considered with respect to all \(2^{j}\) configurations. After that we have \(H H . . . H T T . . . T H \rightarrow H H . . . H H H \rightarrow T T . . T T T\), which is realized exactly by \(j+1+n+1=n+j+2\) moves. It is so, because the number of the \(H\)-coins in the configuration \(H H \ldots H T T \ldots T H\) is \(n+1-(j+1)=n-j\) and the most left \(T\)-coin is \((n-j)\)-th in turn from the left to the right. By \(j+1\) moves we reach \(H H \ldots H H H\) and by \(n+1\) moves we reach \(T T . . . T T T\). The number \(n+j+2\) should be multiplied by \(2^{j}\). If \(j=0\), then the configuration HH...HTH (with only one \(T\)-coin) should be taken into account additionally. Here \(H H \ldots H T H \rightarrow H H \ldots H H H\) by one move and \(H H H \rightarrow T T\)... \(T T T\) by \(n+1\) moves, totally by \(n+2\) moves. Consequently
\[ N_{n+1}=N_{n}+\sum_{j=1}^{n-1}\left(N_{j}+2^{j}(j+1+n+1)+2 n+3\right. \]
In a similar way we find for configurations with length \(n+2\) that
\[ N_{n+2}=N_{n+1}+\sum_{j=1}^{n}\left(N_{j}+2^{j}(j+1+n+2)+2 n+5\right. \]
Then:
\[ \begin{gathered} N_{n+2}=N_{n+1}+\sum_{j=1}^{n} N_{j}+\sum_{j=1}^{n-1} 2^{j}(j+1)+2^{n}(n+1)+(n+1) \sum_{j=1}^{n} 2^{j}+\sum_{j=1}^{n} 2^{j}+2 n+5= \\ =N_{n+1}+N_{n}+\sum_{j=1}^{n-1}\left(N_{j}+2^{j}(j+1+n+1)\right)-\sum_{j=1}^{n-1} 2^{j}(n+1)+2^{n}(n+1)+(n+2) \sum_{j+1}^{n} 2^{j}+2 n+3+2= \\ =2 N_{n+1}+(n+1)\left(2^{n}-\sum_{j=1}^{n-1} 2^{j}\right)+(n+2) \sum_{j=1}^{n} 2^{j}+2= \\ =2 N_{n+1}+(n+1)\left(2^{n}-2^{n}+2\right)+(n+2) \sum_{j=1}^{n} 2^{j}+2=2 N_{n+1}+2(n+1)+(n+2)\left(2^{n+1}-2\right)+2= \\ =2 N_{n+1}+(n+2) 2^{n+1} \end{gathered} \]
Consequently, \(\quad N_{n+2}=2 N_{n+1}+(n+2) 2^{n+1} \quad\) and \(\quad \cfrac{N_{n+2}}{2^{n+2}}=\cfrac{N_{n+1}}{2^{n+1}}+\cfrac{n+2}{2}\). The obtained dependence remains true for all positive integers \(n\). Let \(\cfrac{N_{n}}{2^{n}}=A_{n}\) for each \(n\), which gives us the possibility to express the dependence in the form \(A_{n+1}-A_{n}=\cfrac{n+1}{2}\). Apply this consecutively to \(1,2, \ldots, n\) and take into account that \(A_{1}=\cfrac{1}{2}\), which was proved at the beginning of the solution. Thus:
\[ \begin{gathered} A_{1}=\cfrac{1}{2} \\ A_{2}-A_{1}=\cfrac{2}{2} \\ A_{3}-A_{2}=\cfrac{3}{2} \\ \cdots \cdot \\ A_{n-1}-A_{n-2}=\cfrac{n-1}{2} \\ A_{n}-A_{n-1}=\cfrac{n}{2} \end{gathered} \] Sum up the left and the right hand sides to find that \(A_{n}=2(1+2+\ldots+n)=\cfrac{n(n+1)}{4}\).
NOTES
1. Bogomolny, A. “Reim’s Similar Coins I.” Interactive Mathematics Miscellany and Puzzles. www. cut-the-knot.org/m/Geometry/Reim1.shtml.
REFERENCES
Grozdev, S. (2007). For High Achievements in Mathematics: The Bulgaria Experience (Theory and Practice). Sofia: ADE (ISBN 978-954-92139-1-1).
Rosen, Kenneth H. (2011). Discrete mathematics and its applications (7th ed.). New York: McGraw-Hill (ISBN 978-0-07-338309-5).
Andreescu, T. et al. (2016). Lemmas in Olympiad Geometry. XYZ Press.
Chen, E. (2016). Euclidean Geometry in Mathematical Olympiads. Washington, DC: Mathematical Association of America.