2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I am afraid I don't understand how is this a different question. Or wait. So the interesting case is when they choose an odd number to start with. $\endgroup$ – Matsmath Sep 23 '16 at 12:30
  • 1
    $\begingroup$ @Matsmath the question is not for a specific number, it is asked for any number you may think of... Previous one was only valid for even numbers, odds are included in the odd now. $\endgroup$ – Oray Sep 23 '16 at 12:32
  • $\begingroup$ So I guess then I suggest you to rephrase your question so that they pick an odd number at random. Otherwise I would be inclined to be think that there is 1/2-1/2 probability of randomizing an odd or an even number. Therefore Alice has at least probability of 1/2 of winning. You want to play this game as Alice. $\endgroup$ – Matsmath Sep 23 '16 at 12:37
  • $\begingroup$ @Matsmath It is proven that Alice will win for all the even cases. But not necessarily Bob will win for all odd cases $\endgroup$ – Tejasva Dhyani Sep 23 '16 at 12:54
  • $\begingroup$ Please make up your mind: are they choosing an arbitrary positive integer or an odd one? I wrote an answer assuming the former, realised you'd edited your question to specify oddness and changed my answer accordingly, and now you've edited your question again to remove the oddness criterion. $\endgroup$ – Rand al'Thor Sep 23 '16 at 13:06
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is some pretty interesting stuff here. $\endgroup$ – Matsmath Sep 23 '16 at 13:06
  • $\begingroup$ there is actually easier answer but this one is acceptable too. $\endgroup$ – Oray Sep 23 '16 at 13:09
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.