Maths Olympiad Prep

Library / /92 of 169

Combinatorics Difficulty 7.4 National Olympiad, round 2 Prove it United States

An integer is assigned to each vertex of a regular pentagon so that the sum of the five integers is 20112011. A turn of a solitaire game consists of subtracting an integer mm from each of the integers at two neighboring vertices and adding 2m2m to the opposite vertex, which is not adjacent to either of the first two vertices. (The amount mm and the vertices chosen can vary from turn to turn.) The game is won at a certain vertex if, after some number of turns, that vertex has the number 20112011 and the other four vertices have the number 00. Prove that for any choice of the initial integers, there is exactly one vertex at which the game can be won.

Solution

Let a1,a2,a3,a4a_1, a_2, a_3, a_4, and a5a_5 represent the integers at vertices v1v_1 to v5v_5 (in order around the pentagon) at the start of the game. We will first show that the game can be won at only one of the vertices. Observe that the quantity a1+2a2+3a3+4a4(mod5)a_1 + 2a_2 + 3a_3 + 4a_4 \pmod{5} is an invariant of the game. For instance, one move involves replacing a1,a3a_1, a_3 and a5a_5 by a1m,a3+2ma_1 - m, a_3 + 2m and a5ma_5 - m. Thus the quantity a1+2a2+3a3+4a4a_1 + 2a_2 + 3a_3 + 4a_4 becomes
(a1m)+2a2+3(a3+2m)+4a4=a1+2a2+3a3+4a4+5m, (a_1 - m) + 2a_2 + 3(a_3 + 2m) + 4a_4 = a_1 + 2a_2 + 3a_3 + 4a_4 + 5m,
which is unchanged modulo 55. The other moves may be checked similarly. Now suppose that the game may be won at vertex vjv_j. The value of the invariant at the winning position is 2011j2011j. If the initial value of the invariant is nn, then we must have 2011jn(mod5)2011j \equiv n \pmod{5}, or jn(mod5)j \equiv n \pmod{5}. Hence the game may only be won at vertex vjv_j, where jj is the least positive residue of n(mod5)n \pmod{5}.

By renumbering the vertices, we may assume without loss of generality that the potentially winning vertex is v5v_5. We will show that the game can be won in four moves by adding a suitable amount 2mj2m_j at vertex vjv_j (and subtracting mjm_j from the opposite vertices) on the jjth turn for j=1,2,3,4j = 1, 2, 3, 4. The net change at vertex v1v_1 after these four moves is 2m1m3m42m_1 - m_3 - m_4, which must equal a1-a_1 if we are to finish with 00 at v1v_1. In this fashion we obtain the system of equations
2m1m3m4=a12m2m4=a22m3m1=a32m4m1m2=a4m2m3=a5+2011, \begin{aligned} 2m_1 - m_3 - m_4 &= -a_1 \\ 2m_2 - m_4 &= -a_2 \\ 2m_3 - m_1 &= -a_3 \\ 2m_4 - m_1 - m_2 &= -a_4 \\ -m_2 - m_3 &= -a_5 + 2011, \end{aligned}
which has an integral solution if and only if the game may be won. The sum of the first four equations is the negative of the fifth equation, so the fifth equation is redundant. Multiplying the first four equations by 1,3,3,1-1, 3, -3, 1 and adding them yields 5m25m3=a13a2+3a3a45m_2 - 5m_3 = a_1 - 3a_2 + 3a_3 - a_4. But we are assuming v5v_5 is the potentially winning vertex, so we see
a13a2+3a3a4a1+2a2+3a3+4a4n50(mod5). a_1 - 3a_2 + 3a_3 - a_4 \equiv a_1 + 2a_2 + 3a_3 + 4a_4 \equiv n \equiv 5 \equiv 0 \pmod{5}.
Therefore we may divide by 55 to obtain m2m3=15(a13a2+3a3a4)m_2 - m_3 = \frac{1}{5}(a_1 - 3a_2 + 3a_3 - a_4). We also know that m2+m3=a1+a2+a3+a4m_2 + m_3 = a_1 + a_2 + a_3 + a_4, and one easily confirms that the right-hand sides of these equations are integers with the same parity. Hence the system admits a solution with m2m_2 and m3m_3 integral. The second and third equations then quickly give integer values for m1m_1 and m4m_4 as well, so the system has an integral solution, meaning it is indeed possible to win the game at vertex v5v_5.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.