58th Ukrainian National Mathematical Olympiad

Question

The teacher wrote digits 12391239123 on the board until a 2018-digit number was formed. After that Andriy and Olesya played a game as follows. Alternately (after Andriy begins) they cross out 2 digits as follows: either the first two digits of the number remaining after the previous move, or the last two digits, or the first and last digits of that number. The game ends when the two-digit number is left. Olesya wins, if this number is a multiple of 3, otherwise Andriy wins. Who will win if both players play according to the best strategy? (Bogdan Rublyov)

Accepted Answer

Since we are only interested in divisibility by 3, we can change all the digits as follows: 1, 4, 7 1, 2, 5, 8 2 and 3, 6, 9 3, which will give us the equivalent problem. Then, after 2014 2 = 1007 moves, a 4-digit number will be left on the board, and Olesya will be making the last move. Obviously, these 4 digits left will be the ones that were initially together (following one another) on the board. Therefore, the possible options are: 1231, 2312 or 3123. In either of these cases there is a pair of digits that comprises number 12, and this is exactly the pair which Olesya should leave on the board for her to win.