Library / Berkeley Math Circle: Monthly Contest 2 /14 of 23

Berkeley Math Circle: Monthly Contest 2

Combinatorics Difficulty 5.1 AIME, harder Prove it United States

Problem:

Aerith and Bob take turns picking a nonnegative integer, each time subtracting a (positive) divisor from the other's last number. The first person to pick $0$ loses. For example, if Aerith reached $2020$ on some turn, Bob could pick $2020-20=2000$ , as $20$ is a divisor of $2020$ .
Continuing this example (with Aerith now picking a divisor of $2000$ ), if both of them play optimally, who wins?

Solution

Solution:

If $1998 = 2000 - 2$ were a losing position, Aerith would pick it. Otherwise, she can choose $1999 = 2000 - 1$ . And since this is prime, Bob must pick either $1999 - 1999 = 0$ or $1999 - 1 = 1998$ . In any case, Aerith wins.

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.