Thoughts on a Problem III

I saw an interesting problem recently and can’t resist writing it up. The thought process for this problem was exceedingly unusual as you’ll see later.

First, here’s the source:

But here’s the full problem (rephrased a little) if you’d rather not watch a video.

Problem. From a cylindrical cake with chocolate icing on top, cut successive slices of a fixed angle x. Each slice is then inverted and inserted back into the cake. Find all angles x, such that after finitely many iterations, all the icing is back on top of the cake.

cakeflip

The whole point of the video is to present us with problems whose solutions violate our intuition. This problem is a prime example. At first glance, one might conjecture that the answer is any rational multiple of the full rotation. The correct answer is a little surprising, to say the least.

[ Warning: spoiler ahead with detailed solution. Actually, since this article is about my thoughts on a problem, what else did you expect? šŸ˜› ]

warningThe following solution is to be performed by trained professionals only. Readers please do not attempt to try this on an actual cake.

blue-linSolution

The correct answer is: any angle. Yes, even irrational multiples of the full rotation! This completely bowled me over since for these “irrational angles”, you’ll never cut the same position twice. Fortunately, the professor in the video stopped short of explaining why all angles work, which gives us viewers an opportunity to think this through.

It took me a full 10 minutes to convince myself that “irrational angles” are possible. I realised that after one full round, in passing through the original baseline, the process of flipping the slice also introduces a rather unexpected turn of events.

What I had thought:

cakeflip_1round

What actually transpires:

cakeflip_1round_b

Note that even the initial cutting line had been flipped within the sector.

Upon this realisation, one sees that cutting lines may repeat even though the positions at which you cut don’t, since the cutting lines themselves aren’t stationary. Needless to say, the next step is to see what happens with the second round of cuts. As we continue round, we get:Ā x (brown),Ā x (brown) …

cakeflip_2roundon

Now it should be noted thatĀ a = 2Ļ€-kxĀ for some integerĀ k such thatĀ kxĀ ā‰¤ 2Ļ€ < (k+1)x. AndĀ b =Ā xa = (k+1)x – 2Ļ€. Hence, upon the second round, a sector of the cake is inverted which includes “b” above:

cakeflip_2roundend

The pattern actually got more complex! As the cutting goes through more and more rounds, we’ll certainly expect more interspersing of the colours. How do we prove that it eventually returns to the original pattern?

Turns out there’s a nice way. First we let a andĀ b be as above: a = 2Ļ€ –Ā kx, whereĀ k is the largest positive integer such that kxĀ ā‰¤ 2Ļ€ < (k+1)x. Then letĀ b =Ā x –Ā a = (k+1)x – 2Ļ€. This givesĀ kbĀ + (k+1)aĀ =Ā k(a+b) +Ā a =Ā kx+a = 2Ļ€. Draw a pie chart withĀ k+1 slices of angleĀ a andĀ k slices of angleĀ b. Also highlight the sector where one of edges is the common edge between two slices of angleĀ a (see diagram below); this is the slice we’ll invert.

cakeflip_div

Observe that after inverting this slice, the two anglesĀ a andĀ b are swapped and the next sector is highlighted. This new sector also has one of its edges lying on the common edge between two slices of angleĀ a. Thus, if we consider the total set SĀ of all possible ways to colour each slice with either brown and white (|S| = 2^{2k+1}), then inverting a slice corresponds to a bijective function onĀ S. By elementary theory of permutations, we must eventually get back the original configuration, i.e. all chocolate icing up.

This pretty much solves our problem, although there’s a nagging feeling that the proof may not work if angleĀ x >Ā Ļ€. For this case, we imagine the corresponding problem with angleĀ x’ = 2Ļ€ –Ā x <Ā Ļ€. Instead of inverting a slice of angleĀ x, one imagines inverting a slice of angleĀ x’ then flipping the whole cake over. Hence if, for angle x’,Ā we get back the cake with chocolate icing up inĀ N moves, then for the case of angleĀ x, performingĀ N moves will give us the cake with chocolate icing either all up or all down. In the former case, that’s good; in the latter case, anotherĀ N moves will flip the cake back up.

Conclusion (with apologies to Valve):

cake_not_lie

This entry was posted in Thought and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s