The chocolate bar game: losing positions proved

In my last post I claimed that the losing positions for the chocolate bar game are precisely those of the form $(x_2, x111\dots 1_2)$ (or the reverse), that is, in binary, positions where one coordinate is the same as the other with any number of $1$ bits appended. So things like $(1010, 1010)$ , $(1010, 10101)$ , $(1010, 101011111)$ , $(10101111, 1010)$ , and so on. Let’s prove it!

First, some notation: let’s denote a length- $n$ string of $1$ bits by $1^n$ . (There won’t be any exponentiation in this post so there shouldn’t be any confusion.) Note that $1^0$ denotes the empty sequence of bits. Also, if $x$ and $y$ are sequences of bits, we will write $xy$ to denote their concatenation, that is, the sequence of bits $x$ followed by the sequence of bits $y$ . For example, if $x = 10010$ and $y = 1101$ , then $xy = 100101101$ . (Again, we won’t be doing any multiplication so there should be no confusion.)

Given this notation, we can restate the characterization of losing positions more concisely: the claim is that losing positions are exactly those of the form $(x,x1^n)$ or $(x1^n, x)$ where $x$ is any sequence of bits and $n \geq 0$ is any natural number. Let’s call positions of this form $1$ -padded.

We have two things to prove: first, we have to prove that from every position which is not $1$ -padded, there exists some valid move to a $1$ -padded position. And dually, we also have to prove that from every $1$ -padded position, all possible moves lead to a non- $1$ -padded position—that is, there are no valid moves from one $1$ -padded position to another.¹

For the first part, let $(x,y)$ be a non- $1$ -padded position. Assume that $x > y$ . (Note we can’t have $x = y$ since that would make the position $1$ -padded, with $n = 0$ ; and it’s enough to consider the case $x > y$ since the same argument will apply to the other case where $x < y$ , by symmetry.) Let $n$ be the unique natural number such that $y1^n < x < y1^{n+1}$ . (These inequalities are both strict since the position is not $1$ -padded.) Then I claim that $(x,y) \to (y1^n, y)$ is a legal chocolate bar game move. $x$ is at most one less than $y1^{n+1}$ , that is, $x \leq y1^n0$ . But $y1^n0$ is exactly twice $y1^n$ (adding a zero to the end of a binary number multiplies it by two, just as adding a zero to the end of a decimal number multiplies it by ten). So $y1^n$ is equal to or greater than half of $x$ , and hence a valid move.

Now we must show that from any $1$ -padded position, the only valid moves are to non- $1$ -padded positions. Consider the position $(x1^n, x)$ . (Again, this suffices since the same argument will apply symmetrically to the case $(x,x1^n)$ .) There are two types of moves one could make from this position: one could decrease $x1^n$ , or one could decrease $x$ . First, consider decreasing $x1^n$ , and suppose $n \geq 1$ . Since $x$ stays the same, in order to move to another $1$ -padded position, we must decrease $x1^n$ into something of the form $x1^{n'}$ for some $n' < n$ . That means, at the very least, truncating a $1$ from the end of $x1^n$ —but this is not a legal move, since truncating a $1$ from the end of a binary number decreases it by more than half (in particular it is half rounded down).

So now consider decreasing $x$ (note the following argument works even when $n = 0$ ). In order to reach a $1$ -padded position by decreasing $x$ , we have to end up with something of the form $(x', x'1^{n'})$ where $x' < x$ . But if we decrease $x$ we cannot change $x1^n$ , so in fact $x1^n = x'1^{n'}$ . That means $x'$ has to be a proper prefix of $x$ , and also $x$ has to end in $1$ . But then to decrease $x$ to $x'$ we have to at least truncate a $1$ from the end of $x$ , which we know is not allowed.

Note, finally, that the ultimate losing position $(1,1)$ is trivially $1$ -padded. So we have shown that if you’re in a $1$ -padded position, you are doomed: every possible move you can make leaves a position which is not $1$ -padded, from which we also showed that your opponent can make a move that leaves you back in another $1$ -padded position. Eventually, you will be left with $(1,1)$ and you will lose.

So, to play this game perfectly, you just have to be able to convert numbers into binary in your head. If the position isn’t $1$ -padded, you can always play to decrease the bigger number so it is equal to the smaller number padded by a bunch of $1$ s. If you have to play in a $1$ -padded position for some reason, just play a small move and hope your opponent hasn’t read this blog post.

Technically, we have to prove these at the same time, by simultaneous induction on, say, the sum $x+y$ , but I won’t bother with the picky details.↩

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

4 Responses to The chocolate bar game: losing positions proved

flumdibum2 says:

February 19, 2016 at 7:15 pm

Isn’t an inductive proof much easier?
Say WP are all winning positions, LP all loosing positons.
(1,1) $\in$ LP
(Let’s say we already defined moves etc.)
statement: For any field (m,n) with m <n: (i,j) $\in$ LP $\Longleftrightarrow$ 1 $\leq$ i == j $\leq$ m.
Induction over p = (i,i)
Induction start: p = (1,1) $\Rightarrow$ p $\in$ LP (trivial)
Induction assume: For any strict k: $\forall$ i $\leq$ k: (i,i) $\in$ LP
Induction step(no idea how there are called in english): (p = (i+1,i+1))
All possible moves z from this position can be described with z(i+1,i+1) = (j,k) where
(j == (i+1) $\land$ k < (i+1)) $\lor$ (j < (i+1) $\land$ k == (i+1)).
case 1: (j < (i+1)) $\land$ k == (i+1)) $\Rightarrow$ DO MOVE z' with
z'(i+1,i+1) = ((i+1) – (i+1-k),k) = (k,k).
(k,k) $\in$ LP (see induction assume).
case 2 is equal.
$\Rightarrow$ $\forall$ i: (i,i) $\in$ LP

Now only show that all Positions with are not (i,i) are in WP because you can always create
an (i,i) then. (As already showed in the finish).

This comment section is buggy!
- Brent says:
  
  February 20, 2016 at 2:41 pm
  
  Technically, my proof already was by induction, though I didn’t formally phrase it that way. In any case, your proof works for the game of nim, where you are allowed to decrease either number by any amount. However, in the chocolate bar game, you are only allowed to reduce a number by up to half. In particular, it is not true that all positions not of the form (i,i) can be reduced by a single move to a position of the form (i,i). If k > 2i then (k,i) is a position which cannot be reduced to (i,i).
  - flumdibum2 says:
    
    February 20, 2016 at 2:53 pm
    
    Well looks like I forgot half of the game rules while thinking about it :p
    - Brent says:
      
      February 20, 2016 at 2:55 pm
      
      Haha, no worries. =)