Halve or diminish, and race to unity!

Question

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 1

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.

Answer 2

Call a number winning if a player has a winning strategy when its their turn to play on that number, and losing otherwise.

Every even number is winning.
An odd number $2n-1$ is winning if and only if $n$ is losing.

We prove these two facts by induction.

• Suppose its your turn, and $2n$ is on the board. There are two cases. If $2n-1$ is losing, then subtracting $1$ is a winning strategy (since it leaves your opponent in a losing position). If $2n-1$ is winning, then by induction, $n$ is losing, so dividing by $2$ is your winning move.

• Suppose instead you are faced with $2n-1$. Subtracting $1$ would leave the position $2n-2$ for your opponent, which by induction we know leaves them a winning position, so this is a bad move. Your only potentially sensible move is to halve and round up; this results in $n$, so your only sensible move is a winning move iff $n$ is a losing position.

Since $91720169172016$ is even, the first player wins.

Edit: Here's an explicit condition to determine if a number is winning:

Every $n\ge 2$ is winning iff the binary representation of $n-1$ has an even number of trailing zeroes.

---

Here's a more fleshed out induction proof.

Theorem: For all $n\ge 2$, $n$ is winning if $n=2k$ is even, and $n=2k-1$ is winning iff $k$ is losing.

Proof: By induction on $n$. The base case $n=2$ is easy, since $2$ is clearly winning.

Assume that the theorem holds for $m-1$. There are two cases:

• $m=2k$. Your two options are $m-1=2k-1$ and $k$. Applying the induction hypothesis, $2k-1$ is winning iff $k$ is not, so exactly one of these is a losing position. This means you can leave your opponent a losing position, so $m$ is winning.

• $m=2k-1$. Your two options are $2k-2$ and $k$. By the induction hypothesis, moving to $2k-2$ leaves your opponent a winning position, so is not a winning move. Therefore, you have a winning move iff moving to $k$ is a winning move iff $k$ is a losing position.

Answer 3

Alice is guaranteed to win

Because of a basic symmetry of the game.

Alice starts on an even number, if it is a winning move to halve that number, Alice takes it. If it is not a winning move to halve that number, Alice subtracts instead, and Bob must now halve or subtract. If Bob halves, we know that is a losing move, because it will be the same as if Alice halved, so Bob must subtract. Alice now has priority on an even number again, and because there exists a number less than the starting point where halving it is a winning move, she repeats until she wins.

---

This is reasoning from trying to work it out mathematically, I came up with a better way.

Safest numbers for your opponent to have a turn on are 3, 7, 15, 31, etc., effectively 2f(x-1)+1, because you can always make the move that they don't to keep yourself on the straight path to victory. Unfortunately, the number chosen does not lie particularly near to this pattern. 9 is safe, because halving lets you half again to 3, and subtracting lets you subtract again to 7, which are previously identified as safe. This makes 19, 39, 79, etc., also safe, using the same formula as before. 11 is safe, because it also quarters to 3, and subtracts to 9. This means 23, 47, 95 etc., are safe.

None of these expansions get us particularly close to the starting point yet, but I'm pretty sure I'm on the right path.

Answer 4

Decreasing by one is an odd operation
Halving is an even operation (with caveat of rounding up which may produce odds)
Since Alice goes first, she can always win by watching the total and making sure it is either even or odd as it approaches it's end. How they get to the end does not matter. The last sequence 4,2,1 or 3, 2, 1 is important.
Do the puzzle in reverse. Start at 1 claiming Alice the winner.
A: 1 (+1 or *2) will always be
B: 2 (+1 or *2) will be
A: 3 (+1) or A: 4 (*2), now we have a divergence
B: 3+1 = 4, 3 * 2 = 6, 4 + 1 = 5, 4 * 2 = 8
On this turn we know Alice must have 4,5,6 or 8. Now we can work backwards
Alice has 8, strategy: she halves! B: 4 if he halves, A: does -1, B: 2, A: 1. If at B: 4, he does -1: A: halves, B: 2, A: 1
Alice has 6, strategy: she minus ones! B: 5, he may halve to 3 or sub to 4. At 3, Alice will -1. At 4 Alice will halve, either way B has 2 on his next turn, A: 1
Alice has 5, covered above.
Alice has 4, also covered above.
Basically, Alice knows she can win from 4,5,6,8 and those should be easy numbers to target as the total gets close.

Answer 5

Alice wins!

In order to answer to this question, we need to think from the very beginning: 2. If this game was played from 2, Alice would win by playing $n-1$ or $\left\lceil \frac{n}{2}\right\rceil$.

For $3$: If this game was started from $3$. Alice would lose since her any move would make the next number is $2$:

Since we know whoever plays $2$ wins and $\left\lceil \frac{3}{2}\right\rceil=2$ and $3-1=2$. whoever has $3$ to play loses.

For $4$: $\left\lceil \frac{4}{2}\right\rceil=2$ and $4-1=3$. So whoever has 4 will win since everybody knows $3$ would lose whatever he/she plays and whoever has 4 to play will make $-1$ to make the opponent lose.

As you can understand from the explanation above,

• If $\left\lceil \frac{n}{2}\right\rceil$ and/or $n-1$ loses, whoever has n to play will win,
• If $\left\lceil \frac{n}{2}\right\rceil$ and $n-1$ wins, whoever has n to play will lose whatsoever.

By increasing N with this logic, we can reach the destination date 9/17/2016 (9172016) with the given code:

• In the code, True means Alice wins if she starts from that number, otherwise, Bob wins.
• You may change if (i>9172000) to see all results.

Note: I know there is a pattern but I did not want to bother to follow it since it is very easy to put this question into a code. If you want to understand the pattern, you can take the result from the code if you want instead of trying to solve for every number.