Alice and Bob are playing a game. In the beginning, the integer $9172016$ is written on a blackboard. In a move, a player, can:
- either decrease the number on the board by $1$ (i.e., replace $n$ by $n-1$), or
- halve the number, and round it up to the next integer if a fraction is obtained (i.e., replace $n$ by $\left\lceil \frac{n}{2}\right\rceil$).
As always, Alice moves first, and then they make moves in turns. The first person to get to $1$ wins.
Assuming both players play perfectly, who is going to win the game?
Source: St. Petersburg Math Olympiad, 2001.
Answer
The winner will be
Alice.
More generally,
when the number on the board is even, the player whose turn it is will win.
Proof:
When the number is 2, you can move to 1 and win immediately. Suppose some larger even number is a second-player win (i.e., in this position the player who just played will win with best play). Consider the smallest instance where this happens; call it $2n$. If this position is a second-player win then every position you can move to from it must be a first-player win; in particular $2n-1$ and $n$ are both first-player wins. And since $2n$ is the smallest even-numbered position that's a second-player win, $2n-2$ must also be a first-player win. But now the moves available from $2n-1$ are to $2n-2$ and to $n$; those positions are both first-player wins so $2n-1$ is a second-player win. Contradiction.
No comments:
Post a Comment