Maths Olympiad Prep

Library / /118 of 220

Combinatorics Difficulty 6.0 National Olympiad Prove it Ukraine

299 digits 00 and one digit 11 are written in a circle. The following moves are allowed:
* from each digit, subtract the sum of the adjacent digits;
* select two digits with exactly two digits between them and increase both by 11 or decrease both by 11.

Is it possible to obtain such an arrangement of numbers (after a finite number of such moves), in which there are two adjacent digits 11, and the rest of the digits are 00?

Solution

Let us analyse how the recorded moves affect the sum of the digits written in a circle. Let us denote the numbers by a1,a2,,a300a_1, a_2, \dots, a_{300}. The following numbers will be written after the move of the first type: bk=akak1ak+1b_k = a_k - a_{k-1} - a_{k+1}, k=1,,300k = 1, \dots, 300 (a301a1a_{301} \equiv a_1). Let S=a1+a2++a300S = a_1 + a_2 + \dots + a_{300},

then b1+b2++b300=SSS=Sb_1 + b_2 + \dots + b_{300} = S - S - S = -S. After the move of the second type, the sum becomes S+2S+2 or S2S-2. Since the parity of the sum after each move does not change, it is impossible to get an even sum from the original odd sum.

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.