Communications of the ACM
Last byte
Puzzled: Solutions and Sources
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 Universitaet Berlin) and Pyotr Micek (Jagiellonian 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 cakenot 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−l)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 operation; 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 22k−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.
Footnotes
ALL readers are encouraged to submit prospective puzzles for future columns to [email protected].
DOI: http://doi.acm.org/10.1145/1409360.1409383
©2008 ACM 0001-0782/08/1200 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2008 ACM, Inc.
No entries found