Halve or diminish, and race to unity! v2

Question

This is follow-up question to Halve or diminish, and race to unity!.

Alice and Bob are playing a game. In the beginning, they randomly choose a positive integer between $2$ to $n$ where $n$ is a finite number. 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 has the better chance to win and what is that chance?

Answer 1

Answer

Overall, if an arbitrary (not necessarily odd) number is chosen,

Alice wins with probability $\frac{2}{3}$,

while if we assume that an odd number is chosen,

Bob wins with probability $\frac{2}{3}$.

Proof

As proved by Gareth McCaughan in his excellent answer to the previous question,

any even number is a winning position.

From a number of the form $4k+3$, the only possibilities are to move to $4k+2$ or $2k+2$,

both of which are even, so $4k+3$ is a losing position.

From a number of the form $8k+5$, the only possibilities are to move to $8k+4$ or $4k+3$;

$4k+3$ is a losing position, so $8k+5$ is a winning position.

From a number of the form $16k+9$, the only possibilities are to move to $16k+8$ or $8k+5$,

both of which are winning positions, so $16k+9$ is a losing position.

From a number of the form $32k+17$, the only possibilities are to move to $32k+16$ or $16k+9$;

$16k+9$ is a losing position, so $32k+17$ is a winning position.

We can keep on going in this way to account for all possible positive integers. So Alice's chance of winning, taking all possible $n$ into account (or equivalently, $n=\infty$), is

(proportion of even numbers) + (proportion of $8k+5$ numbers) + (proportion of $32k+17$ numbers) + ... = $\frac{1}{2}+\frac{1}{8}+\frac{1}{32}+\dots = \frac{1}{2}\times\frac{4}{3} = \frac{2}{3}$.

And if we assume the initial number chosen has to be odd, then Alice's overall chance of winning is

(proportion of $8k+5$ numbers) + (proportion of $32k+17$ numbers) + (proportion of $128k+65$ numbers) + ... = $\frac{1}{4}+\frac{1}{16}+\frac{1}{64}+\dots = \frac{1}{4}\times\frac{4}{3} = \frac{1}{3}$, where all proportions are of numbers of the given congruence class among all odd numbers.

Answer 2

We first give an easy way to tell whether a number is a win for Alice.

Theorem: A number $k\ge 2$ is a win for the player about to move if and only if $k-1$ has an even number of trailing zeroes when written in binary.

Ending with zero trailing zeroes is equivalent to being odd, which happens half the time. Ending with 2 trailing zeroes is equivalent to being equal to 4 (mod 8), which happens an eighth of time. Continuing in this fashion, the proportion of numbers which end in $t$ trailing zeroes is $(1/2)^{t+1}$, so the probability a number ends with an even number of such zeroes is $$ \frac12+\frac18+\frac1{32}+\frac1{128}+\dots=\frac23. $$ This gives Alice a roughly 2/3 chance of winning when the number is picked from the range 1...n, with the chance approaching 2/3 as $n\to\infty$. I could give an exact formula, but it would be ugly.

Now, all we have to do is prove the Theorem. Let's say that the height of a number $k$ is the number of trailing zeroes of $k-1$.

Lemma: Halving an odd number and rounding up decreases its height by one.
That is, if $k$ is odd, then height($\lceil k/2\rceil$) = height($k$) – 1.

This is because $k$ has a height of $h$ if and only if $k=m\cdot 2^h+1$ for some integer $m$, and dividing by two and rounding up produces $m\cdot 2^{h-1}+1$.

We prove the Theorem by induction on $k$. The base case $k=2$ holds since $2-1$ has zero trailing zeroes, and is certainly a win for the player about to move.

Assume it holds for all numbers smaller than $k$. There are two cases:

• $k$ is even (so height($k$) = 0). The result of performing the halving move on $k-1$ is $k/2$. By our Lemma, these two numbers have heights which differ by one, so by induction, exactly one of these numbers is losing. Moving to the losing number is a winning move, so $k$ is winning.

• $k$ is odd (so height($k$) > 0). Subtracting one from $k$ leaves an even number. By induction, this leaves a winning position for the next player, so this is a bad move. The only potentially sensible option is to halve $k$, leaving a number with a height which is smaller by one. By induction, this position is losing iff its height is odd, which occurs iff the height of $k$ was even.