, 2023

Combinatorics Difficulty 6.8 National Olympiad Prove it Balkan Mathematical Olympiad

Joe and Penny play a game. Initially there are 5000 stones in a pile, and the two players remove stones from the pile by making a sequence of moves. On the $k$ th move, any number of stones between 1 and $k$ inclusive may be removed. Joe makes the odd-numbered moves and Penny makes the even-numbered moves. The player who removes the very last stone is the winner. Who wins if both players play perfectly?

Solution

If on move $2y - 1$ , Joe removes $1 \le a \le 2y - 1$ stones, then on move $2y$ , Penny can remove either $2y - a$ or $2y + 1 - a$ stones (both of which are in the valid range). Thus Penny can ensure that the two moves remove either $2y$ or $2y + 1$ stones.

If on $k$ occasions, Penny chooses to ensure $2y + 1$ stones are removed then after move $2z$ , there will be
$k + \sum_{y=1}^{z} 2y = z(z + 1) + k$
stones removed. Thus after move $2z$ , Penny can ensure there are any number between $z(z + 1)$ and $z(z + 2)$ stones removed.

Setting $z = 69$ we see that after move $2 \cdot 69 = 138$ , Penny can ensure $69 \cdot 70 \le 4860 \le 69 \cdot 71$ stones have been removed and so there are 140 stones remaining. Joe will leave between 1 and 139 stones which Penny can remove on her turn.

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.