In my last post I claimed that the losing positions for the chocolate bar game are precisely those of the form (or the reverse), that is, in binary, positions where one coordinate is the same as the other with any number of bits appended. So things like , , , , and so on. Let’s prove it!
First, some notation: let’s denote a length- string of bits by . (There won’t be any exponentiation in this post so there shouldn’t be any confusion.) Note that denotes the empty sequence of bits. Also, if and are sequences of bits, we will write to denote their concatenation, that is, the sequence of bits followed by the sequence of bits . For example, if and , then . (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 or where is any sequence of bits and is any natural number. Let’s call positions of this form -padded.
We have two things to prove: first, we have to prove that from every position which is not -padded, there exists some valid move to a -padded position. And dually, we also have to prove that from every -padded position, all possible moves lead to a non--padded position—that is, there are no valid moves from one -padded position to another.1
For the first part, let be a non--padded position. Assume that . (Note we can’t have since that would make the position -padded, with ; and it’s enough to consider the case since the same argument will apply to the other case where , by symmetry.) Let be the unique natural number such that . (These inequalities are both strict since the position is not -padded.) Then I claim that is a legal chocolate bar game move. is at most one less than , that is, . But is exactly twice (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 is equal to or greater than half of , and hence a valid move.
Now we must show that from any -padded position, the only valid moves are to non--padded positions. Consider the position . (Again, this suffices since the same argument will apply symmetrically to the case .) There are two types of moves one could make from this position: one could decrease , or one could decrease . First, consider decreasing , and suppose . Since stays the same, in order to move to another -padded position, we must decrease into something of the form for some . That means, at the very least, truncating a from the end of —but this is not a legal move, since truncating a from the end of a binary number decreases it by more than half (in particular it is half rounded down).
So now consider decreasing (note the following argument works even when ). In order to reach a -padded position by decreasing , we have to end up with something of the form where . But if we decrease we cannot change , so in fact . That means has to be a proper prefix of , and also has to end in . But then to decrease to we have to at least truncate a from the end of , which we know is not allowed.
Note, finally, that the ultimate losing position is trivially -padded. So we have shown that if you’re in a -padded position, you are doomed: every possible move you can make leaves a position which is not -padded, from which we also showed that your opponent can make a move that leaves you back in another -padded position. Eventually, you will be left with 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 -padded, you can always play to decrease the bigger number so it is equal to the smaller number padded by a bunch of s. If you have to play in a -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 , but I won’t bother with the picky details.↩
Isn’t an inductive proof much easier?
Say WP are all winning positions, LP all loosing positons.
(Let’s say we already defined moves etc.)
statement: For any field (m,n) with m <n: (i,j) LP 1 i == j m.
Induction over p = (i,i)
Induction start: p = (1,1) p LP (trivial)
Induction assume: For any strict k: i 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) k < (i+1)) (j < (i+1) k == (i+1)).
case 1: (j < (i+1)) k == (i+1)) 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.
i: (i,i) 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!
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).
Well looks like I forgot half of the game rules while thinking about it :p
Haha, no worries. =)