last byte
DOI: 10.1145/1409360.1409383
Peter Winkler
Puzzled
solutions and sources
Last month (November 2008, p. 112) we posed a trio of brain teasers concerning
circular food shapes. Here, we offer some possible solutions. How did you do?
1. slicing Pizza

Solution. Amazingly, the answer to this puzzle, devised by Dan Brown of California and communicated to me by Dick Plotz of Providence, RI, is “yes,” Baldur may be able to get more than half the pizza. For example, let “ 2” stand for a big slice, “ 1” for a slice half that size, and “0” for a slice that’s negligibly tiny. Then, if the slice sizes (in order around the pizza) are 0, 2,0, 2,0,0, 1,0, 2,0,0, 1,0, 1,0, Baldur gets nearly 5/9 (about 56%) of the pizza no matter what Alta does.

Kolja Knauer and Torsten Uekerdt (graduate students at Technische Uni-versitaet Berlin) and Pyotr Micek ( Jag-iellonian University of Cracow, Poland) sent me a proof that this is as bad as it gets for Alta; she can always guarantee herself at least 4/9 of the pie. Their methods also show that the example here is minimal; Alice can always get half if there are fewer than 15 slices.

Moreover, anytime the number of slices is even (so Baldur gets as many as Alta), Alta is guaranteed half of them, because she can ensure that she gets all the even-numbered slices or all the odd-numbered slices. This is the paradox. It would seem that having an odd number of slices would be advantageous to Alta, since she gets one more slice than Baldur. But in the worst case, the opposite is true.

2. cutting cake

Solution. This intriguing puzzle was sent to me by Thierry Mora, now a postdoctoral student at Princeton’s Institute for Integrative Genomics, who

heard it from his prep-school teacher Thomas Lafforgue in Orsay, France. If you think there is no way that finitely many operations will always get all the frosting back on top, you are not alone. After all, if x is an irrational multiple of 360 degrees, then the cake will never be cut in the same place twice. Therefore, the first cut made will forever alternate between having frosting on its left and not on its right and vice-versa.

The flaw in this reasoning is that because a slice must be rotated in order to invert, the first cut comes up in a different place when a wedge that includes it is turned upside-down.

In analyzing the puzzle, and indeed many serious algorithmic problems as well, it helps to redefine the operation so it is only the “state space”—here, the frosting pattern on the cake—not the operation itself that changes from step to step. In this case, it means rotating the cake after each operation so you always cut in the same place. Accordingly, regarding “north” as 0 degrees, “east” as 90 degrees, and so forth, let us cut always at 0 and minus x. The piece is then flipped over the 0 line to land between 0 and x, while the rest of the cake is rotated clockwise by angle x.

Let k be the smallest number of wedges you must cut to get all the way around the cake; in other words, k is the least integer greater than or equal to 360/x. Let z = x – 360/k and S be the set of cuts at angles 0, x, 2x, 3x, … , (k– 1)x and x–kz, 2x–kz, 3x–kz, … , (k– 1) x–kz. It’s easy to verify that S is closed under the cut-invert-replace opera-

tion; thus, no border between frosted and unfrosted cake can ever appear at an angle not in S. It follows that only finitely many patterns (at most 2^{2k– 1}) are possible. Since the operation is reversible, the cake must cycle back to its original state in at most that many moves. A bit more work shows that the actual number of iterations required is only 2k(k– 1), or just 2k, if 360/x is an integer.

The adventurous among us will find that one can generalize the puzzle, asking that the cake be rotated by another fixed angle y between wedges; it still takes only finitely many operations to get all the frosting back on top.

 

3. Packing circular tarts Note that two tarts (each of half the diameter of the pan) fit snugly in the pan. In any other case, there might be wiggle room. But, who knows? Geometry problems can be tough.

 

All readers are encouraged to submit prospective puzzles for future columns to [e-mail].

Peter Winkler ( [e-mail]) is Professor of mathematics and of computer science and albert bradley Third century Professor in the sciences at dartmouth college, hanover, Nh.