Suppose there is an rectangle. I like to think of it as one of those bars of chocolate made up of squares:

Two players take turns. On a player’s turn, she must break the chocolate bar along any one of the horizontal or vertical lines, and eat the smaller piece (eating the bigger piece would be very rude). [Edited to add: if the pieces are equal, they may eat either piece.] The player who is left with a piece of chocolate, and hence cannot make another move, loses the game. (At least they get to eat the last piece of chocolate.) For example, given the above bar of chocolate, the first player has eight possible moves: she could break it along any one of the 5 vertical lines, or along any of the 3 horizontal lines. However, since she always has to eat the smaller half, some of these moves are really the same. For example, it does not make a difference whether she breaks off and eats the four leftmost squares or the four rightmost squares; in either case her opponent will be left with a bar of chocolate.

Here is an equivalent formulation of the same game: there is a pet store with dogs and cats. Players alternate turns. On a player’s turn, she must decide to buy either some cats or some dogs; once she makes her choice she may buy any number up to, but not exceeding, half the pet store’s inventory of that animal. For example, if the store has 3 cats and 6 dogs, then a player may buy 1 cat, or they may buy 1, 2, or 3 dogs. The loser is whoever’s turn it is when the pet store has only one cat and one dog remaining (since then they are not allowed to buy any).

First, explain why these games are the same.

I actually wrote about this a long time ago (I’m finally getting back around to following up!). In that post I explained how we can visualize the game like this:

(If some of the grid lines appear heavier than others, pay no attention; it is just a rendering artifact.) The square with position (the bottom left is ) represents the game state with an rectangle, or a store with cats and dogs. A square is dark blue if it is a losing position, that is, whoever’s turn it is in this position is going to lose (assuming both players play optimally; practially speaking, of course, a player in a losing position could still win if their opponent makes a bad move). Losing positions are those from which any valid move leads to a winning position (that is, you lose if no matter what you do, your opponent will win). The light blue squares are winning positions: a position is winning if there is at least one valid move to a losing position (that is, you win if there is a move you can make which forces your opponent to lose).

The losing positions in this visualization of the chocolate bar game appear to be arranged in lines whose slope are a (positive or negative) power of two. For example, the central diagonal has a slope of 1; the next line down has a slope of ; the next, ; and so on.

Now, can you explain why the picture looks like this?

Specifically:

1. Can you come up with a relatively simple way to characterize which positions are losing positions and which are winning positions? (Hint: think about the positions in binary.)

2. Use your characterization to devise a strategy for winning the game. Amaze all your friends.

3. Can you prove it? That is, prove that from any losing position (according to your characterization above) the only valid moves are to winning positions, and that from any winning position there always exists at least one valid move to a losing position.

Apparently this problem comes from the 2005 International Olympiad in Informatics. There is a full solution on that site, but it is much too complicated! Of course I will reveal my own solutions in some future posts. Until then, happy solving. Feel free to post comments, questions, partial or full solutions, etc., in the comments (so conversely, don’t look at the comments if you don’t want any spoilers!).