Maths Olympiad Prep

Library / Belarusian Mathematical Olympiad /205 of 208

Belarusian Mathematical Olympiad

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 (So−Se)÷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=b−a−cr = b - a - c. Now the congruence So≡Se(mod11)S_o \equiv S_e \pmod{11} is equivalent to the congruence y≡x+r(mod11)y \equiv x + r \pmod{11}.

If r≡0(mod11)r \equiv 0 \pmod{11}, then BB can use any digit from the set XX as the number xx because the congruence y≡x(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 xi∈Xx_i \in X there exists a digit yi≠xiy_i \ne x_i, yi∈Xy_i \in X such that yi≡xi+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+⋯+y7≡x1+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 7r≡0(mod11)7r \equiv 0 \pmod{11}, which is impossible since r≢0(mod11)r \not\equiv 0 \pmod{11}. Therefore, there exists a number x∈Xx \in X such that y≢x+r(mod11)y \not\equiv x + r \pmod{11} for any digit y∈Xy \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
So−Se=(b+x+y)−(a+c)(1) S_o - S_e = (b + x + y) - (a + c) \quad (1)
for the second case, and
So−Se=(c+x+y)−(a+b)(2) S_o - S_e = (c + x + y) - (a + b) \quad (2)
or
So−Se=(a+x+y)−(c+b)(3) S_o - S_e = (a + x + y) - (c + b) \quad (3)
for the third one.

Set r=a+c−br = a + c - b in (1), r=a+b−cr = a + b - c in (2), and r=b+c−ar = b + c - a in (3).

Therefore, the congruence So≡Se(mod11)S_o \equiv S_e \pmod{11} is equivalent to the congruence x+y≡r(mod11)x+y \equiv r \pmod{11} for all cases. Suppose that for any digit xi∈Xx_i \in X there exists a digit yi∈Xy_i \in X such that xi+yi≡r(mod11)x_i + y_i \equiv r \pmod{11}, yi≠xiy_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 x∈Xx \in X such that y+x≢r(mod11)y+x \not\equiv r \pmod{11} for any digit y∈Xy \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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.