Two greedy chocolate eaters play the following game involving $n$ pieces of chocolate
and an additional parameter $\alpha$ with initial value $1$: Each player eats either $\alpha$
pieces of chocolate or he increments $\alpha$ by $2$ (replacing thus $\alpha$ by $\alpha+2$)
and eats then $\alpha$ pieces of chocolate (he eats thus $2$ pieces more than his opponent
in the preceding move). The game stops if less than $\alpha$ pieces remain and is won
by the player having eaten more. There is thus the possibility of a draw in
the case of equality.
My computer seems to pretend that the first player can always win this game if the initial number of pieces is odd (at least for all odd numbers $\leq 451$).
Is there an easy reason for this?
(In the case of an even number of pieces, the game seems to be more or less balanced
but there are many cases of a draw when both players use optimal strategies.)
Update: I have accepted Douglas Zare's answer containing an elegant explanation for the existence of a winning strategy for the first player. (Un)fortunately, this explanation
does not give much information on the winning strategy and a part of the mystery remains.
Added 4/25/13: The above game is an example of a simple combinatorial game where
the first player has a non-obvious (for most odd values of $n$) winning strategy.
Douglas Zare's proof works also for the following variations
(variation (1) is an even simpler game with less possibilities,
for the remaining ones there are in general more possible moves):
(1) (in honor of Fibonacci): If a player has augmented (by $2$) the number of
pieces, then the next player has to take the same amount (the value of $\alpha$ cannot
be augmented during two consecutive moves).
(2) After a move with $\alpha$ pieces eaten, the next move can eat $\alpha-2,\alpha$
or $\alpha+2$ pieces ($\alpha-2$ has of course to be positive).
(3) Combine (1) and (2): $\alpha-2$ (if positive) or $\alpha$ pieces can always
be eaten, $\alpha+2$ pieces only if $\alpha$ did not increase during the preceding move.
(4) More generally, one can choose for each odd number $\alpha\geq 1$
a set $\mathcal P(\alpha)$ of possible odd numbers for the next value of $\alpha$.
Douglas Zare's proof works if $\mathcal P(1)=\lbrace 1 ,3\rbrace$. A perhaps interesting choice is
$\mathcal P(\alpha)=\lbrace 1,\alpha,\alpha+2\rbrace$ which allows a sort of "reinitialization" of the game.
(5) Variation (4) can be combined with (2): Possible moves depend not
only on the value of $\alpha=\alpha_1$ eaten by the preceding player but also by
the values $\alpha_2,\alpha_3,\dots,\alpha_k$ eaten two moves, three moves etc, ago.
D. Zare's proof applies if $\mathcal P(1,\emptyset,\dots)=\lbrace 1,3\rbrace$ and $\mathcal P(\alpha_1,\dots,\alpha_i,3,1,\emptyset,\dots,\emptyset)\supset\mathcal P(\alpha_1,\dots,\alpha_i,3,\emptyset,\emptyset,\dots,\emptyset)$ for
all choices of $i\leq k-1$ odd numbers $\alpha_1,\alpha_2,\dots,\alpha_i$ .
Are there instances with interesting winning strategies?
Best Answer
Let $n$ be odd. Inductively assume that $n-2$ is a first player win. Suppose eating $3$ is not a winning play for the first player. Then we should eat $1$ first, of course. If the second player responds by eating $1$, we use the winning strategy for $n-2$. If the second player responds by eating $3$, then we use the second player's winning or drawing strategy against a first play of eating $3$. Because that strategy resulted in the second player playing last, it resulted in an even number of chocolates eaten, so there was at least one left. This means we don't run out of chocolates when we use the same strategy after the first play of $1$, so we get the last move and win.
There are a few other relations between whether $1$ or $3$ wins, but I still don't know the full pattern. If $3$ wins for a heap of size $n-4$, then $1$ wins for $n$ by using the strategy for $n-2$ after $(1, 1)$ and the strategy for $n-4$ after $(1,3)$. If $3$ loses for $n-2$, then $1$ wins for $n$, again using the strategy for $n-2$ after $(1,1)$, and stealing second player's response to $3$ in $n-2$ after $(1,3)$.