13
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Can your computer produce sequences of gameplay so you can look for clues? e.g. is $\alpha$ increased a lot, or not very much? Who increases it more? etc. $\endgroup$
    – Will Sawin
    Commented Apr 10, 2013 at 17:20
  • $\begingroup$ I did not try but I have the impression that the winning strategy is rather messy: there is no obvious structure in the even case. $\endgroup$
    – Roland Bacher
    Commented Apr 10, 2013 at 17:28
  • $\begingroup$ By the way, there is an obvious observation: A counterexample does not start with both players eating just $1$ piece since this reduces to the case $n-2$. In other terms, the optimal strategy for the smallest odd value in which the second player can win or force a draw is of the form $1,3,\dots$ or $3,3,\dots$ or $3,5,\dots$ (where I indicate the values of $\alpha$ after the first two moves). $\endgroup$
    – Roland Bacher
    Commented Apr 10, 2013 at 17:35
  • $\begingroup$ If the first player gets the last move, the first player wins. It looks to me like the first player can ensure getting the last move. $\endgroup$
    – Douglas Zare
    Commented Apr 10, 2013 at 18:10
  • 2
    $\begingroup$ If $n=2k^2-1$, the first player can get the last move by blindly playing $1, 3, 5, ..., 2k-1$. $\endgroup$
    – Douglas Zare
    Commented Apr 10, 2013 at 18:46

2 Answers 2

Reset to default
15
$\begingroup$

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)$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I have done a few experiments: For $n$ an odd integer let $w(n)$ denote the of first moves of a winning strategy for the first player. $w(n)$ is a subset of $\lbrace 1,3\rbrace$. (I omit braces for simplicity.) If $w(n)=1$ then either $w(n+2)=1$ or $w(n+2)$ is the whole set of both possible moves $1,3$. If $w(n)$ is the whole set of possible moves then $w(n+2)$ is always a singleton and seemingly more often $3$ than $1$. If $w(n)=3$ then $w(n+2)$ seems to be always $1$. (experimental observations up to $n=249$). $\endgroup$
    – Roland Bacher
    Commented Apr 11, 2013 at 15:56
  • $\begingroup$ Here is a proof that $w(n) = \lbrace 3 \rbrace \implies w(n+2) = \lbrace 1 \rbrace$: There must be a winning strategy for the second player when the first player start with $1$ from $n$. This winning strategy must start with a response of $3$ since $(1,1)$ would reduce to $n-2$, which the first player wins. So, this strategy can be played in response to taking $3$ from $n+2$. $\endgroup$
    – Douglas Zare
    Commented Apr 11, 2013 at 17:03
  • $\begingroup$ There are a few other patterns I have observed experimentally. It appears that if $w(n) = \lbrace 1, 3 \rbrace$ then this is not true for $n-4$, $n-2$, $n+2$, or $n+4$. The next time the winning set seems to be $\lbrace 1, 3 \rbrace$ is $n+6$, $n+8$, or $n+10$. Between two winning sets $\lbrace 1, 3 \rbrace$, sometimes the pattern is $1,1$, sometimes $3,1$, rarely $3,1,1$, and sometimes it is $3,1,1,1$. $\endgroup$
    – Douglas Zare
    Commented Apr 11, 2013 at 17:12
  • $\begingroup$ By the way, little of this depends on the specific structure of the game. The same results are true for variations where $\alpha$ is capped at $5$, or where $\alpha$ increases in the sequence $1,3,15,105,...$. $\endgroup$
    – Douglas Zare
    Commented Apr 11, 2013 at 19:55
  • $\begingroup$ I used a similar strategy-stealing argument here: mathoverflow.net/questions/111794/… $\endgroup$
    – Douglas Zare
    Commented Apr 30, 2013 at 23:11
0
$\begingroup$

Here is a start of an approach which might yield patterns and results. It can be taken further but it might or might not provide a solution.

In the game as given, suppose the goal is to eat more chocolate than the other player (and the greater the discrepancy the better), and it is your turn. It does not matter how much chocolate you have already eaten nor how much the other has, all that matters is the current value of $\alpha$ and the number of remaining squares.

So let $\alpha$ be any positive integer and play with a pile of $s$ stones. The current player can take $\alpha$ or $\alpha+2$ stones, all as before. When no move is possible the player with the fewest stones pays the player with the most stones the difference.

The value of this game to the current player is $$v(\alpha,s)=\max\Big(\ \alpha-v(\alpha,s-\alpha),\alpha+2-v(\alpha+2,s-\alpha-2)\ \Big)$$ provided $s \ge \alpha+2.$ The other cases are $v(\alpha,\alpha)=v(\alpha,\alpha+1)=\alpha$ and $v(\alpha,s)=0$ for $s \lt \alpha.$

In this language, the question is,

Is it the case that $v(1,s)$ is always positive for odd $s?$

So perhaps finding the value of $v(\alpha,s)$ in general (including even $\alpha$) is as easy. It might also be as easy to describe the optimal move. All this is easy to program so I probably did it correctly. I looked at the cases $1 \le \alpha \le 40$ and $\alpha \le s \lt 23\alpha.$ Here are some general and somewhat less general observations which I only guarantee for those cases (although some are true in general and I believe others to be so.)

  • It is almost always (but not always) an advantage to go first so the best move is usually to escalate to $\alpha+2$ sometimes keeping $\alpha$ unchanged is better and sometimes they are equally good.

  • $v(1,s) \gt 0$ with the exceptions $v(1,s)=0$ for $s=6,8,10,12,16,18$ and $v(1,22)=-2$

  • Of the $18040$ cases considered, $11328$ have $v(\alpha,s) \gt 0.$ It also takes the values $0,-2,-4,-6,-8$ with frequencies $710,2274,2222,1326,180$ respectively but nothing smaller (over that range).
  • $v(\alpha,2\alpha+r) \gt 0$ with the exceptions that $v(\alpha,2\alpha+r)=0$ for $r=4,5$ and $\alpha \ge 2r$ and also $v(\alpha,2\alpha+r)=-2$ for $\alpha \ge 2r \ge 12$
  • The smallest observed cases of $v(\alpha,q\alpha+r)=-8$ are for
    • $\alpha=33$ and $[q,r]=[10, 6], [13, -7], [16, -16], [18, 12], [21, 11]$
    • $\alpha=34$ and $[q,r]=[10, 4], [10, 5], [13, -10], [13, -9], [15, 14], [15, 15], [18, 8], [18, 9], [21, 6], [21, 7]$
  • The cases observed with $v(\alpha,q\alpha+r) \le 0$ are listed here.
  • The cases $[\alpha,q,r,v(q\alpha+r)]$ observed which have $v \gt 2\alpha+1$ are $[1, 15, 0, 5], [1, 21, 0, 5], [2, 9, 0, 6], [2, 9, 1, 6], [2, 17, 0, 6], [2, 17, 1, 6], [2, 21, 0, 6], [2, 21, 1, 6]$
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .