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 $x = 1$. Determine whether Aisling or Brendan has a winning strategy for this game.
Problem
Source: Irish Mathematical Olympiad 2023 Problem 7
Tags: combinatorics
14.05.2023 21:29
Aisling wins First she divides $2023$ by $17$. Brendan makes a move on $119$. He can't divide it by $7$ or $17$ or he loses the next move, so he makes it $120$. Now, Aisling makes it $121$. Again, Brendan has to make it $122$ otherwise he loses immediately. Now, Aisling makes it $123$. Again, Brendan has to make it $124$. Now, Aisling divides by $31$ to get $4$. Now, Brendan will lose: if he makes it $2$ he loses and if he makes it $5$ he loses. Therefore, Aisling has a winning strategy
14.05.2023 21:44
leannan-capall wrote: 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 $x = 1$. Determine whether Aisling or Brendan has a winning strategy for this game. Aisling wins First she write $17^2=289$. Brendan must write $290$ because if he write $17$ then Aisling write $1$ and wins.After Aisling write $10$.Now no matter what Brenden does, he will end up with a prime number and Aisling wins