Maths Olympiad Prep

Library / /43 of 56

Combinatorics Difficulty 6.7 National Olympiad Prove it JBMO

Problem:

We have two piles with 20002000 and 20172017 coins respectively. Ann and Bob take alternate turns making the following moves: The player whose turn is to move picks a pile with at least two coins, removes from that pile tt coins for some 2t42 \leqslant t \leqslant 4, and adds to the other pile 11 coin. The players can choose a different tt at each turn, and the player who cannot make a move loses. If Ann plays first determine which player has a winning strategy.

Solution

Solution:

Denote the number of coins in the two piles by XX and YY. We say that the pair (X,Y)(X, Y) is losing if the player who begins the game loses and that the pair (X,Y)(X, Y) is winning otherwise. We shall prove that (X,Y)(X, Y) is losing if XY0,1,7(mod8)X-Y \equiv 0,1,7 \pmod{8}, and winning if XY2,3,4,5,6(mod8)X-Y \equiv 2,3,4,5,6 \pmod{8}.

Lemma 1. If we have a winning pair (X,Y)(X, Y) then we can always play in such a way that the other player is then faced with a losing pair.

Proof of Lemma 1. Assume XYX \geq Y and write X=Y+8k+X=Y+8k+\ell for some non-negative integer kk and some {2,3,4,5,6}\ell \in\{2,3,4,5,6\}. If =2,3,4\ell=2,3,4 then we remove two coins from the first pile and add one coin to the second pile. If =5,6\ell=5,6 then we remove four coins from the first pile and add one coin to the second pile. In each case we then obtain a losing pair.

Lemma 2. If we are faced with a losing distribution then either we cannot play, or, however we play, the other player is faced with a winning distribution.

Proof of Lemma 2. Without loss of generality we may assume that we remove kk coins from the first pile. The following table shows the new difference for all possible values of kk and all possible differences XYX-Y. So however we move, the other player will be faced with a winning distribution.

k\XYk \backslash X-Y017
2564
3453
4342

Since initially the coin difference is 1mod81 \bmod 8, by Lemmas 1 and 2 Bob has a winning strategy: He can play so that he is always faced with a winning distribution while Ann is always faced with a losing distribution. So Bob cannot lose. On the other hand the game finishes after at most 40174017 moves, so Ann has to lose.

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.