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 ⌈n2⌉).
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