Maths Olympiad Prep

Library / /17 of 17

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Croatia

299 zeros and one one are written circular. The following moves are allowed:
* You can select all numbers simultaneously and subtract both of its neighbouring numbers from each number.
* You can select two numbers such that there are exactly two numbers between them, and either increase both selected numbers by 1 or decrease both of them by 1.
Can we obtain through a finite number of moves that the following numbers are written circular:
a) two consecutive ones and 298 zeros?
b) three consecutive ones and 297 zeros?

Solution

Let us analyse how the moves affect certain sums. Denote by aka_k the numbers written at a certain moment, so that a1a_1 is the number written in the place where the one was written before any move was made, and a2,,a300a_2, \dots, a_{300} are the numbers written clockwise from a1a_1. After applying the first type of move, the numbers written are
b1=a1a300a2,bk=akak1ak+1,k=2,,299,b300=a300a299a1. \begin{align*} b_1 &= a_1 - a_{300} - a_2, \\ b_k &= a_k - a_{k-1} - a_{k+1}, \quad k = 2, \dots, 299, \\ b_{300} &= a_{300} - a_{299} - a_1. \end{align*}

a) Observe how the sum of all written numbers changes after each move. If the total sum of numbers aka_k is
S=a1+a2++a300, S = a_1 + a_2 + \cdots + a_{300},
then the sum of numbers bkb_k is
a1a300a2+a2a1a3++a300a299a1=S a_1 - a_{300} - a_2 + a_2 - a_1 - a_3 + \cdots + a_{300} - a_{299} - a_1 = -S
because each aka_k is added once and subtracted twice.

After the second type of move is applied, the sum of all numbers is either S+2S + 2 or S2S - 2. We can conclude that none of the allowed moves changes the parity of the sum of all numbers. Since the sum is 1 (an odd number) in the beginning, we cannot obtain two ones and 298 zeros since their sum is 2 (an even number).

b) Observe how the moves affect the alternating sum. If the alternating sum of numbers aka_k is
S=a1a2+a3+a299a300, S' = a_1 - a_2 + a_3 - \dots + a_{299} - a_{300},
then after applying the first type of move, the alternating sum of numbers bkb_k is
a1a300a2a2+a1+a3+a300+a299+a1=3S, a_1 - a_{300} - a_2 - a_2 + a_1 + a_3 + \dots - a_{300} + a_{299} + a_1 = 3S',
while the alternating sum remains SS' after applying the second type of move. Assume that three consecutive ones and 297 zeros can be obtained. The original alternating sum before any move is made equals 1. When three consecutive ones and 297 zeros are written circular, the alternating sum is either 1 or -1, depending on where the ones are located. Since the allowed moves either triple the alternating sum or they do not affect it, we conclude that the three ones are located so that the alternating sum is 1, and no moves of the first type were allowed.

Observe the sum of numbers in places 3, 6, ..., 300, i.e.
S0=a3+a6++a300. S_0 = a_3 + a_6 + \dots + a_{300}.
Originally, this sum is 0, and when three consecutive ones and 297 zeros are written, that sum is 1. However, applying only the second type of move does not change the parity of that sum. Namely, either none of the numbers a3,a6,,a300a_3, a_6, \dots, a_{300} are changed, or we change exactly two of them by exactly 1, changing S0S_0 by 2 or -2. Since 0 and 1 are of different parity, this shows that we cannot obtain three consecutive ones and 297 zeros.

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 and solution reproduced as published; topic and difficulty added by this site.