Maths Olympiad Prep

Library / /60 of 61

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Belarus

Ann and Bob play the following game. They, in turn (Ann starts), replace one of the asterisks in the expression \overline{*****} by one of the digits from 00 to 99 (each digit can be used exactly one time). Ann wins if the obtained 55-digit 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 So,SeS_o, S_e are the sums of the digits on the odd and even positions respectively in the decimal representation of nn.

Let Ann use the numbers aa, cc, and yy for her first, second, and third moves respectively; let Bob use the numbers bb and xx for his first and second moves respectively.

The following cases are possible after two Ann's moves and one Bob's move:

1. aa and cc occupy two odd positions, bb occupies the even position of the asterisks;
2. aa and cc occupy two even positions, bb occupies the odd position of the asterisks (different from the first position);
3. aa and cc occupy one even and one odd positions, bb occupies the even position of the asterisks.

Let X={x1,x2,,x7}X = \{x_1, x_2, \dots, x_7\} be the set of unused digits before the second Bob's move.

In the first case Bob replaces the asterisk on the even position by xx. Then So=a+c+yS_o = a + c + y, Se=b+xS_e = b + x. Let r=bacr = b - a - c. Now the congruence SoSe(mod11)S_o \equiv S_e \pmod{11} is equivalent to the congruence yx+r(mod11)y \equiv x + r \pmod{11}.

If r0(mod11)r \equiv 0 \pmod{11}, then BB can use any digit from the set XX as the number xx because the congruence yx(mod11)y \equiv x \pmod{11} is impossible if xx and yy are the distinct digits.

Let r≢0(mod11)r \not\equiv 0 \pmod{11}. Suppose that for any digit xiXx_i \in X there exists a digit yixiy_i \ne x_i, yiXy_i \in X such that yixi+r(mod11)y_i \equiv x_i + r \pmod{11}, i=1,2,,7i = 1, 2, \dots, 7. Summing these seven congruences we obtain
y1+y2++y7x1+x2++x7+7r(mod11). y_1 + y_2 + \dots + y_7 \equiv x_1 + x_2 + \dots + x_7 + 7r \pmod{11}.
Since it is evident that y1+y2++y7=x1+x2++x7y_1 + y_2 + \dots + y_7 = x_1 + x_2 + \dots + x_7, we see that the obtained congruence is equivalent to the congruence 7r0(mod11)7r \equiv 0 \pmod{11}, which is impossible since r≢0(mod11)r \not\equiv 0 \pmod{11}. Therefore, there exists a number xXx \in X such that y≢x+r(mod11)y \not\equiv x + r \pmod{11} for any digit yXy \in X different from xx. So Bob can use this number xx for his second move to win.

Consider two other cases. In these cases Bob replaces the asterisk on the odd position (different from the first one) by xx. Then we have
SoSe=(b+x+y)(a+c)(1) S_o - S_e = (b + x + y) - (a + c) \quad (1)
for the second case, and
SoSe=(c+x+y)(a+b)(2) S_o - S_e = (c + x + y) - (a + b) \quad (2)
or
SoSe=(a+x+y)(c+b)(3) S_o - S_e = (a + x + y) - (c + b) \quad (3)
for the third one.

Set r=a+cbr = a + c - b in (1), r=a+bcr = a + b - c in (2), and r=b+car = b + c - a in (3).

Therefore, the congruence SoSe(mod11)S_o \equiv S_e \pmod{11} is equivalent to the congruence x+yr(mod11)x+y \equiv r \pmod{11} for all cases. Suppose that for any digit xiXx_i \in X there exists a digit yiXy_i \in X such that xi+yir(mod11)x_i + y_i \equiv r \pmod{11}, yixiy_i \neq x_i, i=1,2,,7i = 1, 2, \dots, 7. It follows that all digits from XX are partitioned into the pairs of distinct digits with the sum which is congruent to rr modulo 1111, but it is impossible since the number of digits in XX is odd. Therefore, there exists a number xXx \in X such that y+x≢r(mod11)y+x \not\equiv r \pmod{11} for any digit yXy \in X different from xx. So Bob can use this number xx for his second move to win.

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.