Competition problem — Combinatorics

Library / /29 of 42

Combinatorics Difficulty 6.6 National olympiad Prove it Ireland

Aisling and Brendan take alternate moves in the following game. Before the game starts, the number $x = 2023$ is written on a piece of paper. Aisling makes the first move. A move from a positive integer $x$ consists of replacing $x$ either with $x + 1$ or with $x/p$ where $p$ is a prime factor of $x$ .

The winner is the first player to write the number $x = 1$ .

Determine whether Aisling or Brendan has a winning strategy for this game.

Solution

The game is a win for Aisling. Aisling wins by forcing Brendan to write down a prime number, which allows Aisling to claim the prize by writing 1 at the next step.

We say an integer is a 2g-position if it is of the form $2g$ where both $g$ and $2g+1$ are primes (such $g$ are known as Sophie Germain primes). If Aisling can get to a 2g-position then a win is assured, as Brendan is forced to play one of 2, $g$ or $2g+1$ , all of which are prime. The relevant $2g$ positions for this problem are 10 and 58.

Here is one of many possible winning strategies for Aisling.

Aisling divides 2023 by the prime 7, passing 289 to Brendan. As $289 = 17^2$ , Brendan has only two possible next moves: to 290 or to 17. But 17 is prime so Brendan is forced to play 290. If Brendan moves to 290, then Aisling can move to either 10 or 58, both of which are $2g$ positions, so Aisling wins.

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.