The chocolate bar game: losing positions characterized

The evident pattern from my last post is that losing positions in the chocolate bar game appear to be characterized by those (x,y) where the binary expansion of y is the same as the binary expansion of x with any number (including zero) of 1 bits appended to the end (or vice versa): for example, (101, 101), (101, 1011), (101, 10111), and so on.

Appending k ones to the end of the binary expansion of x corresponds to first multiplying x by 2^k (which shifts it left by k places, that is, adds k zeros on the end), and then adding 2^k - 1, which consists of k ones in binary. In other words, losing positions where y \geq x correspond to integer points satisfying

y = 2^k x + 2^k - 1

This is the equation of a line with slope 2^k and with a y-intercept of 2^k - 1. This explains the visual pattern of radiating lines, where the slope of each line is double the previous. It also explains how the lines don’t go through the origin (except for the main diagonal).

If we move 1 to the other side and factor out 2^k, we can also rearrange the above equation as

y + 1 = 2^k(x + 1)

which looks much cleaner; however, I find it much harder to work with. (Though one interesting thing it does show is that although the lines don’t go through the origin, strangely enough they do all go through the point (-1,-1).) In my next post, I will prove that these really are the losing positions, and I’ll stick to the characterization in terms of binary expansions.

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in challenges, games, pattern, pictures and tagged , , , , , , , , . Bookmark the permalink.

One Response to The chocolate bar game: losing positions characterized

  1. Pingback: The chocolate bar game: losing positions proved | The Math Less Traveled

Comments are closed.