Let $N$ be a positive integer. Alberto and Barbara write numbers on a blackboard taking turns, according to the following rules. Alberto starts writing $1$, and thereafter if a player has written $n$ on a certain move, his adversary is allowed to write $n+1$ or $2n$ as long as he/she does not obtain a number greater than $N$. The player who writes $N$ wins. $(a)$ Determine which player has a winning strategy for $N=2005$. $(b)$ Determine which player has a winning strategy for $N=2004$. $(c)$ Find for how many integers $N\le 2005$ Barbara has a winning strategy.
Problem
Source:
Tags: induction, combinatorics unsolved, combinatorics
ocha
10.11.2010 01:58
(a) If Alberto always adds $1$ then he always switches the number on the board from even to odd. And Barbra always makes the number even. Since $2005$ is odd, Alberto must win. (b) Albarto also wins this game. Again Alberto adds $1$ to the number at each turn as long as the number is $\le 500$. If at his turn the number is $\ge 502$ for the first time (it will always be even), then it must also be $\le 1002$ since in the previous move he could have made it at most $501$. At this turn he doubles the number making it at least $1004$ and no more that $2004$. Now Barbra cannot double the number any more so she must add $1$ at each turn. Now Alberto always switches $n$ from odd to even and Barbra always switches from even to odd. Since $2004$ is even, Alberto must win. (c) Edit: deleted
r3d30m3j
10.11.2010 21:11
@ocha: your proof fails in the case $N=8$.
Consider the binary representation of $N$.
If there is no $1$-bit at an even position, Barbara has a winning strategy:
If $k$ is the current position, choose the next position as follows:
Let $e$ be the unique integer s.t. $N/2^{e+1} < k \leq N/2^e$.
If $e$ is even, do the $+1$-move.
Otherwise, do the $*2$-move.
The positions $B$ moves to are exactly the even numbers in the union of intervals $(N/2^{2i+1}, N/2^{2i}]$ (by induction on $i$).
We see that $B$ wins.
Otherwise, Alberto can win:
Let $j$ be the smallest $1$-bit at an even position.
Let $e$ be the unique integer s.t. $N/2^{e+1} < k \leq N/2^e$.
Now, if $e$ is even or $e \geq j$, do the $+1$-move.
Otherwise, do the $*2$-move.
The positions $A$ moves to are the even numbers in the union of intervals $(N/2^{2i+1}, N/2^{2i}]$ for $0 \leq 2i < j$, and the odd numbers in the union of intervals $(N/2^{i+1}, N/2^i]$ for $i \geq j$ (induction again).
Hence $A$ wins.
For part (c), we count the number of integers with all 1-bits in even positions $\leq 2005$. So, $2005_{10} = 01,11,11,01,01,01_{2} \geq 00,10,10,10,10,10_{2}$, so the number of solutions is $0,1,1,1,1,1_{2} = 31_{10}$.