Alice and Bob play the following game: starting with the number $2$ written on a blackboard, each player in turn changes the current number $n$ to a number $n + p$, where $p$ is a prime divisor of $n$. Alice goes first and the players alternate in turn. The game is lost by the one who is forced to write a number greater than $\underbrace{22...2}_{2020}$. Assuming perfect play, who will win the game.
Problem
Source: JBMO Shortlist 2020
Tags: Junior, Balkan, shortlist, 2020, combinatorics, game
sarjinius
04.07.2021 16:02
We claim that Alice will win the game. Since the game must end after a finite number of moves, note that $12$ must be either a "winning number" (i.e. when you write it down, you are in a position to win if you play optimally) or a "losing number" (i.e. when you write it down, your opponent is in a position to win if he/she plays optimally). If $12$ is a winning number, Alice can write $4$, forcing Bob to write $6$. Alice then writes $8$, forcing Bob to write $10$. Alice writes $12$ and can win if she plays optimally. If $12$ is a losing number, Alice can write $4$, forcing Bob to write $6$. Alice then writes $9$, forcing Bob to write $12$. Alice is now in a position to win if she plays optimally. Either way, Alice wins the game.
parmenides51
04.07.2021 17:51
Anna and Basilis play a game writing numbers on a board as follows:
The two players play in turns and if in the board is written the positive integer $n$, the player whose turn is chooses a prime divisor $p$ of $n$ and writes the numbers $n+p$. In the board, is written at the start number $2$ and Anna plays first. The game is won by whom who shall be first able to write a number bigger or equal to $31$.
Find who player has a winning strategy, that is who may writing the appropriate numbers may win the game no matter how the other player plays
was proposed as 2021 Greek JMO p2 here
Lukaluce
04.07.2021 18:17
This problem was proposed by Macedonia
starchan
04.07.2021 18:47
sarjinius wrote: We claim that Alice will win the game. Since the game must end after a finite number of moves, note that $12$ must be either a "winning number" (i.e. when you write it down, you are in a position to win if you play optimally) or a "losing number" (i.e. when you write it down, your opponent is in a position to win if he/she plays optimally). If $12$ is a winning number, Alice can write $4$, forcing Bob to write $6$. Alice then writes $8$, forcing Bob to write $10$. Alice writes $12$ and can win if she plays optimally. If $12$ is a losing number, Alice can write $4$, forcing Bob to write $6$. Alice then writes $9$, forcing Bob to write $12$. Alice is now in a position to win if she plays optimally. Either way, Alice wins the game. Maybe the essence of this point was implied but it's necessary to mention that this is in some sense a perfect information game. A way to see this is by modeling the game states as a directed graph. This type of a game can be shown to always have a definite winner. (The fact that this graph is a DAG is the only useful thing)
Zorger74
27.12.2021 04:47
Solved with zhao_andrew
We claim that $\boxed{\text{Alice}}$ will win, assuming perfect play.
Whichever player writes the number $12$ will either win or lose afterward given perfect play. (We don't know which, but it's fixed, and with perfect play it's assumed that Alice does know.)
The main idea of the solution is that given this fact, Alice can control whether she or Bob writes $12$, causing her to win.
On the first turn of the game, Alice must write $4$. On the second turn, Bob must write $6$. On the third turn, if Alice wants to write $12$, then she can write $8$, Bob must write $10$, and she can write $12$. If Alice wants Bob to write $12$ instead, on the third turn she will write $9$, forcing him to write $12$.
415122
30.03.2022 10:31
Can someone please explain how does having control over the number 12 means we will win? why not some other numbers like 17,19 in place of 12?
Zorger74
30.03.2022 16:50
Vivek1295_9 wrote: Can someone please explain how does having control over the number 12 means we will win? There's no hidden information, so if a specific person has control over a specific number, assuming perfect play, they're guaranteed to win, or guaranteed to lose. Vivek1295_9 wrote: why not some other numbers like 17,19 in place of 12? The statement's true for every number- 17 and 19 would work- but we know that Alice can control 12, which is enough to say she can control the outcome of the game.
415122
30.03.2022 23:57
can you please explain the meaning of perfect play? does the word 'perfect' carry significance?
Zorger74
31.03.2022 00:53
Vivek1295_9 wrote: can you please explain the meaning of perfect play? does the word 'perfect' carry significance? The words "perfect play" basically mean that each player computes the entire game tree and works backwards to determine what their optimal move is, for every move. (The players never make any mistakes, and will force a win if they can) "perfect" definitely carries significance.