Hosted by The Math Forum
Problem of the Week 1101
It's a Piece of Cake
MacPOW Home ||
Math Forum POWs ||
The correct answer is 4, which was found by Witold Jarnicki, Sam VanderVelde, Lyle Ramshaw, John Duncan, John Sullivan, Tim Boykett, Aaron Atlee, Terry Stickels, Philip Roe, and Piotr Zelinski. You might want to skip immediately to the diagram if you did not solve it.
Thanks to all the correspondents on this. If looked at properly the first time, the construction is perhaps not all that interesting. But almost no one looks at it properly the first time. The score among respondents on the list is something like 19 to 10 in favor of the answer 720.
The correct answer is 4. The answer for 1 radian is 84; most will say that the icing never returns to the top in this case because π is irrational. I suspect that the score would even be more lopsided in an experiment where no special encouragement or hint of difficulty was given. Try it on your colleagues with a hintless delivery. They will all say "720."
Here are comments by Peter Winkler (Dartmouth) re. the source:
This wonderful puzzle was passed to me by French graduate student Thierry Mora, who heard it from his prep-school teacher Thomas Lafforgue. The puzzle (of whose origin Lafforgue is unsure) actually involved a second angle as well, indicating the amount of cake passed over between wedges; it STILL requires only finitely many operations to get all the icing back on top, as ambitious readers will verify.
But, the puzzle as stated here (where the second angle is 0) is already surprising and probably challenging enough.
The diagram below shows how four moves do the job. I published a demo showing all the moves in the general case (user inputs the angle, which can be symbolic or numeric) at http://demonstrations.wolfram.com/TheCakeIcingPuzzle/. The general formula for the period is 2k(k - 1) where k is Ceiling[2πA], unless 2π/A is an integer, in which case the answer is clearly just 2k.
Here is a comment from Matt Hancher of NASA Ames Research Center:
Thanks for the great problem! The answer is 4 whenever the angle is 180 + n, where n is between 0 and 180.
Step 0: Pointer at 0, icing on top for (0, 360)
Step 1: Pointer at 180 + n, bottom (0, 180 + n), top (180 + n, 360)
Step 2: Pointer at 2n, bottom (0, 180 + n), top (180 + n, 180 + 3n), bottom (180 + 3n, 360)
Step 3: Pointer at 180 + 3n, bottom (0, 4n), top (4n, 180 + 3n), bottom (180 + 3n, 360)
Step 4: Pointer at 4n, top (0, 360)
And from Ross McConnell, Colo. State Univ.
It takes only four flips! Instead of being blinded by the coordinates around the circle, let's look at a frame of reference that starts at the beginning of the last slice we flipped.
After two flips, the circle, starting at the beginning of the slice you just flipped, is inverted except for the first two degrees of what you just flipped. That means that after four flips, starting at the beginning of the slice you just flipped, the circle is un-inverted, except for the first two degrees of what you just flipped, which weren't inverted anyway after the first two flips. Icing is up all around!
Here is a complete solution to the general problem by Witold Jarnicki (Poland).
Let r be the fraction of the cake corresponding to the angle A. We have the following two cases.
- r = 1/k for some natural k.
- 1/(k + 1) < r < 1/k for some natural k.
Let's solve the cases one by one.
I. It takes 2k moves to put all the icing back to the top. Indeed, divide the cake into k equal sectors and observe the following.
II. It takes 2k(k + 1) moves to put all the icing back to the top. Indeed, divide the cake into sectors counterclockwisely numbered 1, 2, ... , 2k + 1 so that the following hold.
After j-th move (1 ≤ j ≤ k), the first j pieces are flipped and the remaining ones are not.
After (k + j)-th move (1 ≤ j ≤ k), the last k - j pieces are flipped and the remaining ones are not.
The odd-numbered sectors (call them "type A") are of size 1 - kx.
The even-numbered sectors (call them "type B") are of size (k + 1)x - 1.
Note that, the first move:
1) takes one sector of each type,
2) flips them,
3) swaps them and puts them back.
Let us now re-number the sectors so that the numbering starts at the common boundary of the piece just flipped and the piece about to be flipped. Notice that, the properties a) and b) are preserved. Let us consider the numbers to be positions in a queue and look at each move in a bit different (but equivalent) way:
1') take the first two sectors from the front of the queue (one "A" and one "B"),
2') flip them,
3') put them at the end of the queue in opposite order.
Observe now that, we can split the sectors into two queues -- one for "A" elements and one for "B" elements. A move is now equivalent to the following sequence of actions:
1'') take the first sector from the "A" queue,
2'') flip it,
3'') put it at the end of the "A" queue,
1''') take the first sector from the "B" queue,
2''') flip it,
3''') put it at the end of the "B" queue.
Obviously, the cake in the starting problem will have all the icing on the top iff all the sectors in both queues will have the icing on the top. This happens every 2(k + 1) moves in the "A" queue and every 2k moves in the "B" queue (see case I). Therefore, the solution is
lcm(2(k + 1), 2k) = 2lcm(k + 1, k) = 2k(k + 1)/gcd(k*k + 1) = 2k(k + 1).
For a right angle, we have r = 1/4. This is case I, k = 4, i.e., 8 moves.
For a 180° angle, we have r = 1/2. This is case I, k = 2, i.e., 4 moves.
For a 181° angle, we have r = 181/360. This is case II, k = 1, i.e., 4 moves.
For a 1 radian angle, we have r = (1/2)pi. This is case II, k = 6, i.e., 84 moves."
Here is the diagram showing the solution, using 185° instead of 181° for clarity. The answer is 4 for any angle between 180° and 360°.
[Back to Problem 1101]
© Copyright 2008 Stan Wagon. Reproduced with permission.