Maths Olympiad Prep

Library / /39 of 39

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Italy

Problem:

An equilateral triangle is divided into 9 small triangles as in the figure, and on each small triangle the number 0 is initially written. Marco, to pass the time, plays the following game: at each move he chooses 2 small triangles sharing a side and adds or subtracts 1 to both numbers written on these triangles (it is understood that the operation performed on the two triangles is the same). After some time he notices that the numbers written on the 9 small triangles are, in some order, n,n+1,,n+8n, n+1, \ldots, n+8, where nn is a non-negative integer. Prove that nn can only be 0 or 2.

Figure 1

Note. The cases n=0n=0 and n=2n=2 can actually occur, but it is not required to prove this statement.

Solution

Solution:

As in the figure, we number the small triangles from T1T_{1} to T9T_{9} and color red the triangles T1,T2,T4,T5,T7,T9T_{1}, T_{2}, T_{4}, T_{5}, T_{7}, T_{9}, leaving the other 3 white. Letting mim_{i} be the number written in the triangle TiT_{i} at a certain moment, we show that the sum over the white triangles is equal to that over the red ones, that is
m1+m2+m4+m5+m7+m9=m3+m6+m8. m_{1}+m_{2}+m_{4}+m_{5}+m_{7}+m_{9}=m_{3}+m_{6}+m_{8}.
Figure 2
Certainly equality (1) holds at the beginning of the game, before Marco makes any move, since both sides of (1) equal 0. We show that, at every move, the equation remains true. Whichever 2 neighboring small triangles are chosen, one is white and the other is red; therefore only one mim_{i} on the right and only one mjm_{j} on the left of equation (1) are modified. Notice, however, that both are either incremented or decremented by 1, so if the equality was satisfied before performing the move it will also be satisfied after applying it.

Suppose now that
{m1,,m9}={n,,n+8}\left\{m_{1}, \ldots, m_{9}\right\}=\{n, \ldots, n+8\}. Whichever 3 integers among these are chosen, their sum cannot exceed (n+8)+(n+7)+(n+6)(n+8)+(n+7)+(n+6), from which
m3+m6+m83n+21 m_{3}+m_{6}+m_{8} \leq 3 n+21
similarly, choosing 6 integers in the set {n,,n+8}\{n, \ldots, n+8\}, their sum is at least equal to the sum of the 6 smallest, hence
m1+m2+m4+m5+m7+m96n+15. m_{1}+m_{2}+m_{4}+m_{5}+m_{7}+m_{9} \geq 6 n+15.
Combining the last two inequalities with (1) we obtain
6n+15m1+m2+m4+m5+m7+m9=m3+m6+m83n+21, 6 n+15 \leq m_{1}+m_{2}+m_{4}+m_{5}+m_{7}+m_{9}=m_{3}+m_{6}+m_{8} \leq 3 n+21,
which implies 3n63 n \leq 6, that is n2n \leq 2. It remains to exclude that n=1n=1 can occur. In that case m1++m9=1++9=45m_{1}+\cdots+m_{9}=1+\cdots+9=45, which is an odd number. However, every move of Marco changes the sum m1++m9m_{1}+\cdots+m_{9} by +2 or -2 (depending on whether he chooses to add or subtract from the two neighboring small triangles); since this sum equals 0 at the beginning of the game, it always remains even (and in particular different from 45), so the case n=1n=1 is impossible.

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 translated into English from it; metadata (topic, difficulty) added by this project.