Maths Olympiad Prep

Library / /65 of 65

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it Romania

Alina and Bogdan play the following game. They have a heap and 330330 stones in it. They take turns. In one turn it is allowed to take from the heap exactly 11, exactly nn or exactly mm stones. The player who takes the last stone wins. Before the beginning Alina says the number nn, (1<n<101 < n < 10). After that Bogdan says the number mm, (mnm \neq n, 1<m<101 < m < 10). Alina goes first. Which of the two players has a winning strategy? What if initially there are 20182018 stones in the heap?

Adapted from a Belarus Olympiad problem

Solution

• For the heap initially containing 330330 stones:

Bogdan has a winning strategy. One such strategy is the following:

1. If Alina chooses a number nn which is not a multiple of 33, then Bogdan chooses m=2m = 2 (or any other number that is not a multiple of 33 in case Alina has chosen n=2n = 2);
2. If Alina chooses 33 or 99, Bogdan chooses 55;
3. If Alina chooses 66, Bogdan chooses 44.

In the first case, the number of stones Alina leaves in the heap is not a multiple of 33; Bogdan will take 11 or 22 stones, leaving a heap with a number of stones multiple of 33. Thus, at the end, Bogdan is the one that leaves 00 stones in the heap.

If Alina chooses an odd number, in particular 33 or 99, Bogdan can choose mm odd and whatever Alina moves, he can always take one stone from the heap. After Alina's moves, the heap will always contain an odd number of stones, so she cannot win.

If Alina chooses 66, Bogdan chooses 44 and he will move as follows: if Alina takes 11 or 66 stones, Bogdan takes 44, and if Alina takes 44, Bogdan takes 11. Thus, after Bogdan's moves the number of stones in the heap will always be a multiple of 55, while after Alina's moves it will not be a multiple of 55. Bogdan wins again.

• For the heap initially containing 20182018 stones:

Alina has a winning strategy. One such strategy is the following:

She chooses n=2n = 2.

- If Bogdan chooses m{4,5,7,8}m \in \{4, 5, 7, 8\}, Alina moves such that the number of stones she leaves in the heap is always a multiple of 33 (initially she takes 22 stones).
- If Bogdan chooses m=3m = 3, Alina moves such that the number of stones she leaves in the heap is always a multiple of 44 (initially she takes 22 stones). (If Bogdan takes 11, 22 or 33 stones, Alina takes 33, 22, and 11 stone(s), respectively, leaving a number of stones that is a multiple of 44.)
- If Bogdan chooses m=6m = 6, Alina moves such that the number of stones she leaves in the heap gives one of the remainders 00 or 33 when divided by 77 (initially she takes 22 stones). Later, if Bogdan finds 7k7k stones in the heap and takes 11, 22 or 66 stones, then Alina takes 66, 22, or 11 stones, respectively, while if Bogdan finds 7k+37k + 3 stones in the heap and takes 11, 22 or 66 stones, Alina takes 22, 11, or 11 stones, respectively.
- If Bogdan chooses m=9m = 9, Alina moves such that the number of stones she leaves in the heap gives one of the remainders 00, 33 or 66 when divided by 1010 (initially she takes 22 stones). Later, if Bogdan finds 10k10k stones in the heap and takes 11, 22 or 99 stones, then Alina takes 99, 22, or 11 stones, respectively, leaving 10(k1)10(k - 1) or 10(k1)+610(k - 1) + 6 stones. If Bogdan finds 10k+310k + 3 stones in the heap and takes 11, 22 or 99 stones, Alina takes 22, 11, or 11 stones, respectively, leaving 10k10k or 10(k1)+310(k - 1) + 3 stones. (The last situation is possible only if k0k \neq 0). If Bogdan finds 10k+610k + 6 stones in the heap and takes 11, 22 or 99 stones, Alina takes 22, 11, or 11 stones, respectively, leaving 10k+310k + 3 or 10(k1)+610(k - 1) + 6 stones. (The last situation is possible only if k0k \neq 0).

Thus, irrespective on Bogdan's choice of mm, Alina wins by choosing n=2n = 2.

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.