Euclid's game

Rules — Euclid's game

• You start with two numbers.
• On your turn you subtract a multiple of the smaller one from the larger one: once, twice, three times… as many as you like.
• What you leave can never be negative, so there is a limit to how many times you may subtract.
• Whoever leaves a zero wins.

Levels:

• Level 1 — numbers up to 25.
• Level 2 — numbers up to 60.
• Level 3 — numbers up to 200.

Against the computer you also choose who starts. It matters: from some pairs the player to move can always win, and from others they cannot.

The pair is 30 and 7. The smaller one is 7, so you may take away 7, or 14, or 21, or 28 — four different moves, because 4 × 7 = 28 still fits inside 30 and 5 × 7 = 35 does not. Here the last one is chosen, and the pair becomes 7 and 2.

Notice where the choice comes from: the larger number was more than four times the smaller. When the larger is less than twice the smaller, there is only one legal move and you have no say at all — the game plays itself until the ratio opens up again.

So the real question on every turn is not "how much do I take away" but what do I hand over: a pair where my opponent gets to choose, or a pair where they are forced. Play a few games and see which of the two is the good one to give away.