Maths Olympiad Prep

Library / /23 of 27

Combinatorics Difficulty 6.9 National olympiad Prove it Croatia

Two players alternately write one digit at a time, from left to right. A player loses if, after his move, there is a sequence of digits a1,a2,,ana_1, a_2, \dots, a_n such that there exists a positive integer kk for which the number akak+1an\overline{a_k a_{k+1} \dots a_n} is a multiple of 1111.

Which player can win regardless of how his opponent plays? (Russia 2003)

Solution

We will show that the second player can win regardless of the first player's actions. Obviously, none of the players will write 00 in any step.

Notice that 10r(1)r(mod11)10^r \equiv (-1)^r \pmod{11}, so the following criterion for divisibility by 1111 holds:
akak+1ananan1+an2+(1)nkak(mod11) \overline{a_k a_{k+1} \dots a_n} \equiv a_n - a_{n-1} + a_{n-2} - \dots + (-1)^{n-k} a_k \pmod{11}
Denote by NkN_k the remainder when dividing akak+1an\overline{a_k a_{k+1} \dots a_n} by 1111, for k=1,,nk = 1, \dots, n. If, after the nthn^{th} move, the numbers N1,,NnN_1, \dots, N_n are pairwise distinct, then by the mentioned criterion, in the next move we obtain the numbers an+1N1,,an+1Nn,an+1(mod11)a_{n+1} - N_1, \dots, a_{n+1} - N_n, a_{n+1} \pmod{11} which are also pairwise distinct since an+10a_{n+1} \neq 0. Inductively, we conclude that after each step of the game (for n10n \le 10), the numbers N1,,NnN_1, \dots, N_n are distinct. Because of the way in which N1,,NnN_1, \dots, N_n transform at each move, we conclude that there are at most n+1n+1 digits which, if the player writes them, will cause him to lose.

Assume that the game lasts for at least nine moves. The second player loses if and only if, after the ninth move, the set {N1,N2,,N9}\{N_1, N_2, \dots, N_9\} is {1,2,,9}\{1, 2, \dots, 9\}, i.e. the second player wins if and only if 1010 is among the numbers N1,N2,,N9N_1, N_2, \dots, N_9.

If, after the eighth move, {N1,...,N8}\{N_1, ..., N_8\} lacks two numbers between 11 and 1010 which are not consecutive, then, no matter what the first player chooses in the ninth move, one of the numbers N1,...,N9N_1, ..., N_9 must be 1010. Namely, if the first player chooses XX, then there is kk such that Nk=X+1N_k = X + 1 (in eighth move). Hence, after the ninth move we obtain
NkX(X+1)110(mod11). N_k \equiv X - (X + 1) \equiv -1 \equiv 10 \pmod{11}.
Let us show that the second player can ensure that after the eighth move, among the numbers N1,...,N8N_1, ..., N_8 there are no two consecutive numbers. Certainly, the second player can ensure that the game lasts at least seven moves. Let
{N1,...,N7}={1,2,...,10}{X,Y,Z}. \{N_1, ..., N_7\} = \{1, 2, ..., 10\} \setminus \{X, Y, Z\}.
If among the numbers XX, YY and ZZ there are no consecutive ones, then the second player can choose any of them. If Y=X+1Y = X + 1, then the second player can write one of the numbers XX or X+1X + 1 so that, after the eighth move, there are two consecutive numbers missing from N1,...,N8N_1, ..., N_8. Namely, if Z=X1Z = X - 1, the second player writes XX, and if ZX1Z \neq X - 1, the second player writes X+1X + 1.

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 and solution reproduced as published; topic and difficulty added by this site.