Breaking Chocolate

Alright, new puzzle time. I'm a bit surprised I hadn't posted this puzzle before, as I thought of it many years ago. Anyway, I sort of came up with it myself, but I may have had some influence from Carl Michal. Also, this game appears exactly in Winning Ways For Your Mathematical Plays, so I cannot claim that that book didn't give me inspiration. Anyway, on to the puzzle:
Consider a two player game in which the players take turns breaking up an NxM block of chocolate. On a players turn, they select one existing block of chololate and break it in a straight line along one of its break lines making two smaller blocks of chocolate. The players alternate turns, selecting a single block and breaking it into two smaller blocks. If on a players turn they have no legal moves (because there are only 1x1 blocks left), they lose. Determine the optimal strategy and who will be the winning player from a starting NxM position.

To clarify, a legal move is to select an available NxM block, then select a positive integer k less than N or a positive integer i less and M and turn that NxM block into either a (N-k)xM block plus a kxM block, or into a Nx(M-i) block plus a Nxi block. To give some examples, in the 1x1 case the first player loses (having no legal moves), and in the 1x2 case the first player wins (by making the only legal move).

3 comments:

Anonymous said...

Maybe I'm mistaken, but is there even an optimal strategy? To me, the solution seems independent of the actual cuts/breaks made.

Consider an (internal) corner-point for the breaks: when the game has finished, it will either have been broken in the vertical direction first (one break), and then in the horizontal direction twice, or the other way around.

Both ways are equivalent, and can in fact be switched without changing the total number of breaks (though some instantations will not have a physical realization).

The external corners give no choice.

Thus, the number of breaks made is constant at (M-1)+M(K-1), and only depends on M and K.

Kory Stevens said...

You have the essentials of it, though your proof is quite different than mine, I feel that there is a subtle issue in your proof with the fact that a single break has an effect on multiple corners at once, but maybe I'm just missing a point there.

Anyway, you are right that this isn't actually a game, but figuring out exactly why it isn't a game makes for a neat puzzle, at least I think so.

Anonymous said...

True, but in each corner you can rotate the (local) break independently. You can/will end up with unphysical "half-breaks" (a break in one corner not lining up with the break in the neighboring corner), which are not realizable. But every break pattern can be described by just looking at the corners.

Thanks for the puzzle/problem again!