Library / /6 of 36

, 2023

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Baltic Way

Fifty marbles are lying in a heap. Alfred and Bodil take turns in removing a positive number of marbles, Alfred starts and at each step the number of marbles removed needs to be a prime or a square. The winner is the one who empties the heap. Who wins if both play in an optimal way?

Solution

We make a table inductively that shows whether the player, whose turn it is if there are $n$ marbles left, wins (marked with a W) or loses (marked with an L).

$n$	1<br>W<br>-1	2<br>W<br>-2	3<br>W<br>-3	4<br>W<br>-4	5<br>W<br>-5	6<br>L	7<br>W<br>-1	8<br>W<br>-2	9<br>W<br>-3	10<br>W<br>-4
$n$	11<br>W<br>-5	12<br>L	13<br>W<br>-1	14<br>W<br>-2	15<br>W<br>-3	16<br>W<br>-4	17<br>W<br>-5	18<br>L	19<br>W<br>-1	20<br>W<br>-2
$n$	21<br>W<br>-3	22<br>W<br>-4	23<br>W<br>-5	24<br>L	25<br>W<br>-1	26<br>W<br>-2	27<br>W<br>-3	28<br>W<br>-4	29<br>W<br>-5	30<br>L
$n$	31<br>W<br>-1	32<br>W<br>-2	33<br>W<br>-3	34<br>W<br>-4	35<br>W<br>-5	36<br>W<br>-36	37<br>W<br>-7	38<br>L	39<br>W<br>-1	40<br>W<br>-2
$n$	41<br>W<br>-3	42<br>W<br>-4	43<br>W<br>-5	44<br>L	45<br>W<br>-1	46<br>W<br>-2	47<br>W<br>-3	48<br>W<br>-4	49<br>W<br>-5	50<br>L

The proof of the correctness of the table is inductive. If there are at most 35 marbles left, a player cannot remove a number of marbles of the type

6k

with

k \in \mathbb{Z}

, because the numbers 6, 12, 18, 24 and 30 are neither prime numbers nor squares. We can conclude inductively that, as long as

n \le 35

, the number

n

should be marked with an L if it is divisible by 6 (since a legal move will yield a number that is not divisible by 6), and it should be marked with a W if it is not divisible by 6 (since removing 1, 2, 3, 4 or 5 marbles yields to a number that is divisible by 6).

This argument is not valid for $n = 36$ , as one can remove all 36 marbles in one step and thus win.

The number $n = 37$ is also winning, since one can remove 7 marbles to bring the opponent into a losing position with 30 marbles.

With $n = 38$ marbles left it is not possible to win, since one would need to remove $38 - 30 = 8$ , $38 - 24 = 14$ , $38 - 18 = 20$ , $38 - 12 = 26$ , $38 - 6 = 32$ or all 38 marbles to bring the opponent into a losing position, but the numbers 8, 14, 20, 26, 32 and 38 are neither prime numbers nor squares.

The next five numbers, 39, ..., 43 are winning positions, because a removal of 1, ..., 5 marbles leaves the opponent in the losing position with 38 marbles.

However, $n = 44$ is again a losing position, because one would need to remove $44 - 38 = 6$ , $44 - 30 = 14$ , $44 - 24 = 20$ , $44 - 18 = 26$ , $44 - 12 = 32$ , $44 - 6 = 38$ or all 44 marbles to force the opponent into a losing position, but these moves are not allowed.

The next five numbers, 45, ..., 49 are winning positions, because a removal of 1, ..., 5 marbles leaves the opponent in the losing position with 44 marbles.

Now the number 50 is left and it is again a losing position, because Alfred would need to remove $50 - 44 = 6$ , $50 - 38 = 12$ , $50 - 30 = 20$ , $50 - 24 = 26$ , $50 - 18 = 32$ , $50 - 12 = 38$ , $50 - 6 = 44$ or all 50 marbles to bring Bodil into a losing position, but these moves are not allowed. Hence Bodil will win the game if she plays in an optimal way.

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.