# Halve or diminish, and race to unity!

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.

• By halving the number do we halve 9172016 or just 2016 like the example? – Beastly Gerbil Sep 17 '16 at 10:59
• We halve whatever we have on the board at that moment. At the first move, we halve 9172016 – Ankoganit Sep 17 '16 at 12:09
• Can you clarify and then they make alternating moves? This sounds like if A negates by one, then B must divide by 2, and then A must negate by one, etc... – Matsmath Sep 17 '16 at 13:55
• @Matsmath Ok, I edited the question for more clarity. :) – Ankoganit Sep 17 '16 at 15:23
• @Ankoganit are u Gamow? – Oray Sep 17 '16 at 15:48

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.

• I think most people would agree that this is mind-blowingly elegant. :) – Ankoganit Sep 18 '16 at 2:53

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.

• Very nice! I was puzzled by the odd condition (especially, what happens with numbers of the form 2^k+1 (mod 2^k)), but I could get nothing sensible. I was thinking of doing something similar, but somehow the inductions relied on each other (that is, for the first statement I should have proved the second already, and the other way around...). Can you kindly detail the steps of the induction (starting point, hypothesis, moving from k->k+1)? – Matsmath Sep 18 '16 at 2:41
• @Matsmath Indeed, the induction is a bit weird. I can add the details, gonna have to be tomorrow though – Mike Earnest Sep 18 '16 at 2:53

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.

• You make a fatal mistake in your reasoning: if Alice halves n, then Bob is to move on n/2; on the other hand, if Bob halves, then Alice to move on n/2. These are different states of the game. – Matsmath Sep 17 '16 at 20:49
• @Matsmath "Fatal mistake"? Who is playing doesn't change a state from being a losing state or winning state (for the current player). If Alice doesn't want to halve, then Bob doesn't want to halve either. – ffao Sep 17 '16 at 23:50
• Look... Assume that whoever gets number n/2, have a winning strategy. Now we are on n, and Alice to move. Alice does not want to halve, because then Bob would have a winning move starting from n/2. So Alice subtracts. Then Bob is to move from n-1. Here, Bob does not want to halve either, because this case Alice would be able to move from n/2, and would win. Both players avoid halving, contrary to what you have claimed. – Matsmath Sep 18 '16 at 0:09
• @Matsmath the point is, since Alice starts on an even number, Bob never gets an opportunity to half that Alice hasn't seen before until Alice halves, and she can just avoid halving until she's on a path that guarantees victory. – Sconibulus Sep 18 '16 at 0:18
• @Sconibulus I am afraid I don't understand your comment. There is also no path guaranteeing victory as the recursion (see below my comment to Oray's answer) determines for each position whether it is a winning or losing. Alice's win or lose, based on optimal strategy, is determined by its starting position, and by only that. – Matsmath Sep 18 '16 at 0:34

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.

• I guess this is not meant to be a complete solution. Also, what do you mean by 'odd' and 'even' operations? – Ankoganit Sep 17 '16 at 15:15
• I think, he means odd function and even function... – Sid Sep 17 '16 at 15:31
• @Sid Seriously? $x\mapsto x-1$ is not an odd function, nor is $x\mapsto \frac{x}{2}$ even... ;) – Ankoganit Sep 17 '16 at 15:37
• @Ankoganit It's not?? Well, I don't know maths... I was just guessing.. – Sid Sep 17 '16 at 15:40
• Pardon me, I typed in a hurry before breakfast. I meant a function for generating 'odd' and 'even' numbers to manipulate them into a win situation for Alice. Now that I think of it, this riddle is very much like the game of Go. – ansielf Sep 17 '16 at 17:25

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.

• Your post wants to indicate, that f[n]=1-f[ceiling(n/2)]*f[n-1], and that solving this recursion with the initial value f[2]=1 yields f[9172016]=1. – Matsmath Sep 17 '16 at 20:50