Maths Olympiad Prep

Library / /42 of 87

Combinatorics Difficulty 6.3 National Olympiad Prove it Russia

Initially 100100 numbers 11 are arranged on a circle. Petya and Vasya play the following game, taking turns; each boy performs 101010^{10} moves; Petya starts. By his move, Petya chooses 99 consecutive numbers and decreases each of them by 22. By his move, Vasya chooses 1010 consecutive numbers and increases each of them by 11. Prove that Vasya can play so that after each his move among the numbers on the circle there will be at least 55 positive numbers (regardless of Petya's moves).

Solution

Let the numbers written in a circle be denoted as a1,a2,,a100a_1, a_2, \dots, a_{100}. Vasya will track only ten numbers, which he will pair as follows: (a9,a18)(a_9, a_{18}), (a27,a36)(a_{27}, a_{36}), \dots, (a90,a99)(a_{90}, a_{99}). In one move, Petya can decrease at most one of these 1010 numbers. If Petya decreases one number in a pair (ai,ai+1)(a_i, a_{i+1}), Vasya will respond by adding 11 to each of ai,ai+1,,ai+9a_i, a_{i+1}, \dots, a_{i+9}. If Petya doesn't decrease any of these 1010 numbers, Vasya will make any allowed move.

Thus, after each pair of moves (Petya's and Vasya's), the sum of numbers in each of Vasya's five pairs will not decrease. Since initially all five pair sums are positive, after each of Vasya's moves the sum in each pair will remain positive, meaning each pair will contain at least one positive number. Therefore, after any of Vasya's moves there will be at least 55 positive numbers, as required.

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.