Competition problem — Combinatorics

Library / /35 of 60

Combinatorics Difficulty 6.2 National olympiad Prove it Ukraine

The teacher wrote digits $123\ldots9123\ldots9123\ldots$ 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)

Solution

Since we are only interested in divisibility by $3$ , we can change all the digits as follows: $1, 4, 7 \to 1$ , $2, 5, 8 \to 2$ and $3, 6, 9 \to 3$ , which will give us the equivalent problem. Then, after $2014 \div 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.

Looking for a route rather than 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.