Maths Olympiad Prep

Library / /178 of 224

Combinatorics Difficulty 6.8 National Olympiad Prove it Belarus

The odd number of the asterisks are written on the blackboard: 2n+1\underbrace{**\dots*}_{2n+1}.
Ann and Bob play the following game. They, in turn (Ann starts), replace one of the asterisks in the expression 2n+1\underbrace{**\dots*}_{2n+1} by any of the digits from 00 to 99 (the first left asterisk cannot be replaced by 00). Ann wins if the obtained number is divisible by 1111, otherwise Bob wins.
Who of the players wins if both of them play to win?

Solution

Answer: Bob wins.
It is well-known that a natural number nn is divisible by 1111 if and only if (SoSe)÷11(S_o - S_e) \div 11, where SoS_o, SeS_e are the sums of the digits on the odd and even positions respectively in the decimal representation of nn.
Let 2n+12n + 1 (nNn \in \mathbb{N}) asterisks be written on the blackboard: 2n+1\underbrace{**\dots*}_{2n+1}.
Show Bob's winning strategy. If Ann replaces some asterisk (different from the first one) by cc, then, in answer, Bob replaces asterisk of the opposite parity by the same digit cc (note that Bob always chooses the asterisk different from the first one). Thus, if at the end Ann replaces the first asterisk by some digit dd, then SoSe=dS_o - S_e = d. Since d0d \neq 0 we see that the obtained number is not divisible by 1111.
If Ann replaces the first asterisk by some digit c0c \neq 0 and it is not her last move, then Bob replaces some even asterisk by c1c-1, and further he keeps the strategy described above. As the result in the end Ann must replace some odd asterisk by some digit dd. Therefore, in this case SoSe=d+c(c1)=d+1S_o - S_e = d + c - (c - 1) = d + 1. Since dd is a digit we have 0<d+1<110 < d + 1 < 11, so the obtained number is not divisible by 1111, and Bob wins.

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.