Upside Down Cake

[gavinksong]

(This puzzle is from a blog called By Way Of Contradiction.)

Imagine you have a circular cake, that is frosted on the top. You cut a d degree slice out of it, and then put it back, but rotated so that it is upside down. Now, d degrees of the cake have frosting on the bottom, while 360 minus d degrees have frosting on the top. Rotate the cake d degrees, take the next slice, and put it upside down. Now, assuming the d is less than 180, 2d degrees of the cake will have frosting on the bottom.

If d is 60 degrees, then after you repeat this procedure, flipping a single slice and rotating 6 times, all the frosting will be on the bottom. If you repeat the procedure 12 times, all of the frosting will be back on the top of the cake.

For what values of d does the cake eventually get back to having all the frosting on the top?

[plasmid]

If the slice size is a rational number of degrees, you can express it as (numerator/denominator) degrees. After you make (360 x denominator) cuts, you will have progressed (numerator) times around the cake and be back at your initial position. Importantly, you will have made a finite number of cuts, and every subsequent cut that you make after that will fall at the same position as one of the previous cuts you made.

That allows you to define the "state" of the problem as follows: There are some finite number of equally spaced positions that will ever be cut in the cake, and every segment of cake between adjacent pairs of cutting positions will be entirely frosting up or entirely frosting down. So going clockwise from the current position of the person cutting the cake, you can describe it as a series of "up"s or "down"s indicating the position of the frosting on the next segment. If there are S segments in the cake, then there are 2^S possible states that the problem can be in.

The next important fact is: For any state, you can calculate what the next state will be after flipping the next slice, and you can also tell what the previous state must have been by working backwards – there is only one possible state that could have led to the current state.

Now for the solution. If you start at state {up, up, up, … up} and you start the cutting and flipping process, then after you make 2^S steps you must have visited at least one of the states twice. Call the first state that you visit twice "state T". State T must be the initial state: {up, up, up, … up}. Suppose state T is not the initial state - then it must have been preceded by some state that I'll call (T-1), but because T has been visited twice and (T-1) is the only state that can lead to T, that would imply that state (T-1) must have been visited twice so T wouldn't actually be the first state that was visited twice. Therefore, the first state to be visited twice must be the initial state.

If that argument's tough to follow, you can think of it more like making a chain from state to state where, if every link of the chain must be connected to exactly one preceding link and exactly one subsequent link, the only way to assemble a finite number of links without any loose ends is into a circle.

If d is irrational, define a "transition" as any point in the cake where it switches from being frosting up to frosting down or vice-versa. There are three things that can happen when you flip a piece of cake:

1) If there are an even number of transitions between the two slice positions, then the two edges of the piece would initially either both be frosting-up or both be frosting-down, and after flipping they would both be in the opposite orientation from which they started. So if there were originally no transition at a slice point before the flip then a transition would be introduced there by the flip, and if there were a transition at a slice point before the flip then that transition would be eliminated by the flip.

2) If there are an odd number of transitions between the two slice positions, then the two edges of the piece would initially be in opposite positions, and after the flip the edges would end up being in the same orientation that they started in. So there would be neither creation nor destruction of transitions at the slice points.

3) Regardless of whether #1 or #2 occurs, every transition within the cut piece would end up at a position given by the following formula:

(Original transition point) - (First slice point) (mod 360) = (Second slice point) - (Transition point after flipping) (mod 360)

So

(Transition point after flipping) (mod 360) = (First slice point) + (Second slice point) - (Original transition point) (mod 360)

Now consider what happens when you start cutting and flipping. First you'll introduce a transition at 0 degrees. The cutter will eventually make it around the cake so on cut number N = 360/d (rounded up) he will cut out a piece that contains that original transition. Relative to the cutter before making slice #N, the position of that transition is 360-((N-1)*d) degrees. So its new position after flipping (if all measurements are made relative to the first slice that will be made) will be:

(First slice point) + (Second slice point) - (Original transition point) (mod 360)

= (0) + (d) - (360-((N-1)*d)) (mod 360)

= d + (N-1)*d - 360 (mod 360)

= N*d

That's relative to the cutter before making the flip; after making the flip and moving ahead d degrees, the transition point would be (N-1)*d degrees ahead of the cutter.

Now consider the following description of the life cycle of any transition point.

A) The only way to generate a transition is through process #1, which will generate a transition at a slice point: either the cutter's current position or the cutter's current position plus d.

B) As the cutter progresses around the cake, that transition point will move (relative to the cutter) d degrees backward with each cut.

C) Eventually when the cutter makes cut #N after initially passing the transition point, he'll flip a piece containing the transition so the transition point will move to (N-1)*d degrees ahead of the cutter (by the math from the previous paragraph).

D) The cutter reaches the transition point again after N slices and either destroys it with process #1 or leaves it alone with process #2. If the latter, then we start over at point A of this loop and repeat until the transition eventually gets destroyed.

The important point from that is that every transition must fall at some (positive or negative) multiple of d degrees away from the cutter's current position, with an integer coefficient from -N+1 to N-1. So define the "state" of the system as the set of positions where there are transition points relative to the cutter. There are a finite number positions that can be transitions. Also note that you can solve for this process in reverse: given a set of transitions, there is only one state that could have led to any given current state. Having a finite number of available states and having a one-to-one correspondence between any given state and the states that must precede and follow it means that there must be a loop by the same argument given for rational slice sizes.

Also for completeness: this only proves that all transitions will eventually be eliminated, which might have the cake in either an "all frosting up" or "all frosting down" configuration. If it's in an "all frosting down" configuration when all of the transitions are eliminated, then simply repeat the entire process once more and it will be "all frosting up".

[plasmid]

What happens when you make it around the circle if d is not divisible by 360? For example, if d is 200 degrees, then after the first cut&flip the cake from 0-200 degrees will be frosting down and the cake from 200-360 degrees will be frosting up. You'll then make a slice covering the last 160 degrees that wasn't covered already, plus another 40 degrees.

Does every point on the cake within the area that gets flipped go from being frosting up to frosting down, as if it were inverted on its vertical axis or as if all slices including previously made cuts are rotated independently? Or does the entire 200 degree slice get rotated en-bloc around an axis going from the middle of its arc to the center of the circle (regardless of whether there are already previously made cuts within that slice)?

In the figure, if the cake has blue frosting and the cutter is green, the first of those scenarios would produce the outcome on the top and the second scenario would produce the outcome on the bottom when he's about to make the third slice.

[gavinksong]

What happens when you make it around the circle if d is not divisible by 360? For example, if d is 200 degrees, then after the first cut&flip the cake from 0-200 degrees will be frosting down and the cake from 200-360 degrees will be frosting up. You'll then make a slice covering the last 160 degrees that wasn't covered already, plus another 40 degrees.

Does every point on the cake within the area that gets flipped go from being frosting up to frosting down, as if it were inverted on its vertical axis or as if all slices including previously made cuts are rotated independently? Or does the entire 200 degree slice get rotated en-bloc around an axis going from the middle of its arc to the center of the circle (regardless of whether there are already previously made cuts within that slice)?

In the figure, if the cake has blue frosting and the cutter is green, the first of those scenarios would produce the outcome on the top and the second scenario would produce the outcome on the bottom when he's about to make the third slice.

Cake slices.jpg

Plasmid,

You may imagine the cake to stick back together after returning a slice. If you make another slice and flip it, the entire slice is rotated en bloc. You may end up rotating the cake by over 360 degrees.

I hope that answers all of your questions.

[bonanova]

I played with this puzzle, or one very much like it, back when I first joined Brainden, back in 2007. I have some of the figures I drew for it, but I can't locate the posts. So I can't reconstruct the solution. What I do recall was the answer was surprising and difficult to see even when given. I also can't locate the source I had. Thinking it was one of Martin Gardner's books, but it eludes my present search. I'll watch this one being solved here again.

[plasmid]

It doesn't seem that difficult to see, at least for the solution I came up with.

If the slice size is a rational number of degrees, you can express it as (numerator/denominator) degrees. After you make (360 x denominator) cuts, you will have progressed (numerator) times around the cake and be back at your initial position. Importantly, you will have made a finite number of cuts, and every subsequent cut that you make after that will fall at the same position as one of the previous cuts you made.

That allows you to define the "state" of the problem as follows: There are some finite number of equally spaced positions that will ever be cut in the cake, and every segment of cake between adjacent pairs of cutting positions will be entirely frosting up or entirely frosting down. So going clockwise from the current position of the person cutting the cake, you can describe it as a series of "up"s or "down"s indicating the position of the frosting on the next segment. If there are S segments in the cake, then there are 2^S possible states that the problem can be in.

The next important fact is: For any state, you can calculate what the next state will be after flipping the next slice, and you can also tell what the previous state must have been by working backwards – there is only one possible state that could have led to the current state.

Now for the solution. If you start at state {up, up, up, … up} and you start the cutting and flipping process, then after you make 2^S steps you must have visited at least one of the states twice. Call the first state that you visit twice "state T". State T must be the initial state: {up, up, up, … up}. Suppose state T is not the initial state - then it must have been preceded by some state that I'll call (T-1), but because T has been visited twice and (T-1) is the only state that can lead to T, that would imply that state (T-1) must have been visited twice so T wouldn't actually be the first state that was visited twice. Therefore, the first state to be visited twice must be the initial state.

If that argument's tough to follow, you can think of it more like making a chain from state to state where, if every link of the chain must be connected to exactly one preceding link and exactly one subsequent link, the only way to assemble a finite number of links without any loose ends is into a circle.

On the other hand, suppose the slice size is irrational. Then you will never make a slice that falls at the exact same position as a previous slice. If you were to do so, then count the number of slices you've made since starting the process and say you've made two slices at the exact same position on slice number N and slice number M. In that case, you must have made (M-N) slices that must have traversed some integer C circumferences of the cake or (C*360) degrees, so the slice size must be (C*360)/(M-N) degrees, which is a rational number and not the scenario we're dealing with.

Since no slice will fall at the position of a previous slice, you know that the cake just to the left of the new slice will be in the same orientation (up or down) as the cake just to the right of the new slice. So after you flip that piece, the segment that came from just to the left of the new slice will end up flipped in the opposite orientation as the segment just to the right of the new slice, and you will never reach a state where the entire cake is uniformly all up or all down.

[gavinksong]

It doesn't seem that difficult to see, at least for the solution I came up with.

If the slice size is a rational number of degrees, you can express it as (numerator/denominator) degrees. After you make (360 x denominator) cuts, you will have progressed (numerator) times around the cake and be back at your initial position. Importantly, you will have made a finite number of cuts, and every subsequent cut that you make after that will fall at the same position as one of the previous cuts you made.

That allows you to define the "state" of the problem as follows: There are some finite number of equally spaced positions that will ever be cut in the cake, and every segment of cake between adjacent pairs of cutting positions will be entirely frosting up or entirely frosting down. So going clockwise from the current position of the person cutting the cake, you can describe it as a series of "up"s or "down"s indicating the position of the frosting on the next segment. If there are S segments in the cake, then there are 2^S possible states that the problem can be in.

The next important fact is: For any state, you can calculate what the next state will be after flipping the next slice, and you can also tell what the previous state must have been by working backwards – there is only one possible state that could have led to the current state.

Now for the solution. If you start at state {up, up, up, … up} and you start the cutting and flipping process, then after you make 2^S steps you must have visited at least one of the states twice. Call the first state that you visit twice "state T". State T must be the initial state: {up, up, up, … up}. Suppose state T is not the initial state - then it must have been preceded by some state that I'll call (T-1), but because T has been visited twice and (T-1) is the only state that can lead to T, that would imply that state (T-1) must have been visited twice so T wouldn't actually be the first state that was visited twice. Therefore, the first state to be visited twice must be the initial state.

If that argument's tough to follow, you can think of it more like making a chain from state to state where, if every link of the chain must be connected to exactly one preceding link and exactly one subsequent link, the only way to assemble a finite number of links without any loose ends is into a circle.

On the other hand, suppose the slice size is irrational. Then you will never make a slice that falls at the exact same position as a previous slice. If you were to do so, then count the number of slices you've made since starting the process and say you've made two slices at the exact same position on slice number N and slice number M. In that case, you must have made (M-N) slices that must have traversed some integer C circumferences of the cake or (C*360) degrees, so the slice size must be (C*360)/(M-N) degrees, which is a rational number and not the scenario we're dealing with.

Since no slice will fall at the position of a previous slice, you know that the cake just to the left of the new slice will be in the same orientation (up or down) as the cake just to the right of the new slice. So after you flip that piece, the segment that came from just to the left of the new slice will end up flipped in the opposite orientation as the segment just to the right of the new slice, and you will never reach a state where the entire cake is uniformly all up or all down.

An admirable attempt, plasmid - but incorrect

Your explanation was very rigorous, but you overlooked something critical.

all rational numbers, if I understood correctly

I'm honestly somewhat surprised, because your questions seemed to suggest that you would not make this mistake.

Edited October 19, 2014 by gavinksong

[plasmid]

That statement of my current answer is correct, and could be amended with "and no other solutions exist".

Try as I might, I can't see a loophole where the argument would break down. One point that might be worth clarifying in case it's causing problems:

When I speak of segments that are formed between adjacent slices, I'm talking about taking the set of all slices that are made anywhere on the cake after going around howevermany times it takes to come back and make a slice exactly at the original starting point, and defining a segment as the area between any two slices that are closest together -- NOT defining a segment as the area between two slices that were made in two consecutive steps (like the first piece of cake that gets cut out and flipped).

Can you give a counterexample, or would it be too much of a blatant hint if you did?

[gavinksong]

That statement of my current answer is correct, and could be amended with "and no other solutions exist".

Try as I might, I can't see a loophole where the argument would break down. One point that might be worth clarifying in case it's causing problems:

When I speak of segments that are formed between adjacent slices, I'm talking about taking the set of all slices that are made anywhere on the cake after going around howevermany times it takes to come back and make a slice exactly at the original starting point, and defining a segment as the area between any two slices that are closest together -- NOT defining a segment as the area between two slices that were made in two consecutive steps (like the first piece of cake that gets cut out and flipped).

Can you give a counterexample, or would it be too much of a blatant hint if you did?

I can't give you a counterexample, but I can suggest that you look at the diagram that you drew in your first post again.

The puzzle is just designed to cause people to make the same mistake you made.

The answer to the question you asked in that post is significant. Don't ignore it.

The correct solution isn't as crazy as bonanova made it seem, though I suppose it may be confusing at first glance. Don't let him scare you.

[plasmid]

If the green guy in the picture continues to make cuts going around the circle counterclockwise, after making n cuts he will have moved 200*n degrees. That becomes a multiple of 360 when he reaches a total of 1800 degrees, or after 9 cuts.

 

After he's made it around the circle and made all of the cuts, there will be a cut at every 360/9 = 40 degrees. So you can define the segments

 

S1 = 0-40 degrees

S2 = 40-80 degrees

S3 = 80-120 degrees

S4 = 120-160 degrees

S5 = 160-200 degrees

S6 = 200-240 degrees

S7 = 240-280 degrees

S8 = 280-320 degrees

S9 = 320-360 degrees

 

Before starting the cutting, all segments will be frosting up, so the state of the problem can be denoted by a vector of 9 "UP"s

[uUUUUUUUU]

 

After the first cut from 0 degrees to 200 degrees, segments S1-S5 will all be flipped and now be frosting down. Also, the green guy will have moved 200 degrees and will have segment S6 just in front of him and will have segment S5 just behind him. I've defined the state of the problem as a series of "UP/DOWN"s starting from the position of the cutter, so the state of the problem will be

[s6, S7, S8, S9, S1, S2, S3, S4, S5] which would be

[uUUUDDDDD]

 

To get to the next state, consider the five pieces that will be cut out next: [s6,S7,S8,S9,S1] = [uUUUD]. After cutting and flipping them, their new orientation will be [uDDDD] and they will be moved from the front to the end of the vector describing the state. So the new state would be

[DDDDUDDDD]

which is in agreement with the bottom figure from my post earlier.

 

That gives you a feel for how to go from one state to the next when you make a cut and flip, so I won't go through the work in much detail for the next steps.

 

From [DDDDUDDDD]: take the [DDDDU] at the beginning, flip it to [DUUUU], and move it to the end, and you get [DDDDDUUUU].

 

From [DDDDDUUUU]: take the [DDDDD] at the beginning, flip it to [uUUUU], and move it to the end, and you get [uUUUUUUUU]. So now you're back at having all pieces with frosting up.

[karthickgururaj]

I didn't read plasmid's solution, but came up with the same end result (seems that keeps happening to me)..

 

 

Starting with only integral values for 'd', if d were a factor of 360, it must be obvious that after 360/d operations the cake will be completely upside-down. And after twice as many, the cake would have flipped back to its original position. For d = 60^o, it will take 2*(360/60) = 12 operations; for d = 1^o, it will take 720 operations.

 

If 'd' is not a factor of 360 (for example, say d = 7^o), then, after completing 360 degrees, a "residue" of the cake will be in a different state than the rest of the cake. In our example, that residue is, 52*7 - 360 = 4 degrees. So 4^o worth of cake will be frosting-side up, rest will be frosting side down. Note that the residue is always lesser than the value of 'd'. If we repeat this process once more around the cake, the residue will increase to 8^o.. So, taking d = 7^o and going around the cake once (52 times), is as if we started with d = 4^o and did the operation once. The solution is then apparent, keep continuing until the "residue" flips the whole cake over. In this case, it will happen after 2*(360/4) rotations of the cake.

 

Of course, it is possible that the "residue" is not an factor of 360, For example, if d = 17, the residue left after one rotation is: 22*17-360 = 14 deg. But that is not a problem! Because the residue of the residue can be a factor of 360.

 

And since each "residue" is lesser than the value of 'd' (or the previous residue), the process needs to converge.

 

In other words, the cake will be flipped over eventually, for all integral values of 'd'.

 

For rationals expressed as p/q (with p and q being co-prime), performing the operation 'q' times is the same as performing the operation once with d = p. So the cake will be flipped for all rational 'd' as well.

 

It remains to prove that all irrational values of 'd' can't "flip" the cake over. This can also be shown... approach can be similar..

 

[gavinksong]

If the green guy in the picture continues to make cuts going around the circle counterclockwise, after making n cuts he will have moved 200*n degrees. That becomes a multiple of 360 when he reaches a total of 1800 degrees, or after 9 cuts.

After he's made it around the circle and made all of the cuts, there will be a cut at every 360/9 = 40 degrees. So you can define the segments

S1 = 0-40 degrees

S2 = 40-80 degrees

S3 = 80-120 degrees

S4 = 120-160 degrees

S5 = 160-200 degrees

S6 = 200-240 degrees

S7 = 240-280 degrees

S8 = 280-320 degrees

S9 = 320-360 degrees

Before starting the cutting, all segments will be frosting up, so the state of the problem can be denoted by a vector of 9 "UP"s

[uUUUUUUUU]

After the first cut from 0 degrees to 200 degrees, segments S1-S5 will all be flipped and now be frosting down. Also, the green guy will have moved 200 degrees and will have segment S6 just in front of him and will have segment S5 just behind him. I've defined the state of the problem as a series of "UP/DOWN"s starting from the position of the cutter, so the state of the problem will be

[s6, S7, S8, S9, S1, S2, S3, S4, S5] which would be

[uUUUDDDDD]

To get to the next state, consider the five pieces that will be cut out next: [s6,S7,S8,S9,S1] = [uUUUD]. After cutting and flipping them, their new orientation will be [uDDDD] and they will be moved from the front to the end of the vector describing the state. So the new state would be

[DDDDUDDDD]

which is in agreement with the bottom figure from my post earlier.

That gives you a feel for how to go from one state to the next when you make a cut and flip, so I won't go through the work in much detail for the next steps.

From [DDDDUDDDD]: take the [DDDDU] at the beginning, flip it to [DUUUU], and move it to the end, and you get [DDDDDUUUU].

From [DDDDDUUUU]: take the [DDDDD] at the beginning, flip it to [uUUUU], and move it to the end, and you get [uUUUUUUUU]. So now you're back at having all pieces with frosting up.

I apologize, plasmid. It seems that you did not overlook what I thought you did. However, your final answer is still wrong.

Of course, your proof of rational numbers isn't. It's pretty solid, except for one leap in the logic. I will point it out. In this previous example, you assert that a total of nine distinct cuts will be made in the cake. However, as you worked out the solution, you only had to make four slices before returning to your initial position, which means there are at most five distinct cuts that are ever made. That may seem innocuous - in fact, you may have even been aware of this, since you probably knew that your loop did not necessarily have to traverse all the states that you defined. However, it does punch a hole in your logic as it raises the question of what defines a valid state in the first place, when your current algorithm for finding valid states appears to be arbitrarily lenient. This is significant because your proof against irrational number solutions relies on the fact that you can't formulate a finite number of states in the same manner that you did for your proof for rational numbers. It is still perfectly possible, that even when your definition generates a countably infinite number of states, a subset of these states still form a loop.

[gavinksong]

I didn't read plasmid's solution, but came up with the same end result (seems that keeps happening to me)..

Starting with only integral values for 'd', if d were a factor of 360, it must be obvious that after 360/d operations the cake will be completely upside-down. And after twice as many, the cake would have flipped back to its original position. For d = 60^o, it will take 2*(360/60) = 12 operations; for d = 1^o, it will take 720 operations.

If 'd' is not a factor of 360 (for example, say d = 7^o), then, after completing 360 degrees, a "residue" of the cake will be in a different state than the rest of the cake. In our example, that residue is, 52*7 - 360 = 4 degrees. So 4^o worth of cake will be frosting-side up, rest will be frosting side down. Note that the residue is always lesser than the value of 'd'. If we repeat this process once more around the cake, the residue will increase to 8^o.. So, taking d = 7^o and going around the cake once (52 times), is as if we started with d = 4^o and did the operation once. The solution is then apparent, keep continuing until the "residue" flips the whole cake over. In this case, it will happen after 2*(360/4) rotations of the cake.

Of course, it is possible that the "residue" is not an factor of 360, For example, if d = 17, the residue left after one rotation is: 22*17-360 = 14 deg. But that is not a problem! Because the residue of the residue can be a factor of 360.

And since each "residue" is lesser than the value of 'd' (or the previous residue), the process needs to converge.

In other words, the cake will be flipped over eventually, for all integral values of 'd'.

For rationals expressed as p/q (with p and q being co-prime), performing the operation 'q' times is the same as performing the operation once with d = p. So the cake will be flipped for all rational 'd' as well.

It remains to prove that all irrational values of 'd' can't "flip" the cake over. This can also be shown... approach can be similar..

This problem is more interesting than it looks at first glance. Unfortunately, although you did get the same answer as plasmid, in some respects, his reasoning for rational numbers is slightly "more correct" - partially because it's more general and less prone to error. Your remainder argument pretty much sums to a confirmation of the existence of a least common multiple between 360 and any rational number, which would normally be sufficient but I'm afraid the OP is slightly trickier than that.

The slices are flipped, not inverted.

[plasmid]

Edit: misunderstood the point you were making in the previous post, will think about it some more.

It's saying that the part showing which numbers can lead to an all-up position again is ok, but the part saying that there are no other solutions is not convincingly rigorous, correct?

Edited October 21, 2014 by plasmid

[gavinksong]

Edit: misunderstood the point you were making in the previous post, will think about it some more.

It's saying that the part showing which numbers can lead to an all-up position again is ok, but the part saying that there are no other solutions is not convincingly rigorous, correct?

That is correct. Although to be clear, it isn't just that your proof isn't convincing or rigorous enough, the result is also incorrect.

There are irrational numbers that work as well.

[gavinksong]

I realize that my hints haven't been very helpful, so here's to make mends. What plasmid said about cuts never being made in the same place if d is irrational is actually false.

[bonanova]

Yeah.

 

Now we're at the point where the "obviously" impossible case is being asserted to be possible.

Somewhere around 2008 I thought through the process to see it, but I can't do it again now.

I love the clarity of the arguments being made here.

I can't provide the answer, but I hope to understand it once again when it's explained.

[plasmid]

I think I see what you (gavinksong) are getting at now, and also why you couldn't give a counterexample... that seems like it would actually be very hard to do. But it would probably be necessary in order to show that any of the values of d that I excluded as unable to reach all-up again could actually reach that state, or at least come up with a proof that such a solution must exist even if you can't explicitly solve for it.

It might take me a while to come up with a decent argument for the existence or nonexistence of such a solution.

[phil1882]

pi or a multiple thereof?

Edited October 22, 2014 by phil1882

[gavinksong]

pi or a multiple thereof?

Nope. The answer is much simpler.

[gavinksong]

I didn't read plasmid's solution, but came up with the same end result (seems that keeps happening to me)..

Starting with only integral values for 'd', if d were a factor of 360, it must be obvious that after 360/d operations the cake will be completely upside-down. And after twice as many, the cake would have flipped back to its original position. For d = 60^o, it will take 2*(360/60) = 12 operations; for d = 1^o, it will take 720 operations.

If 'd' is not a factor of 360 (for example, say d = 7^o), then, after completing 360 degrees, a "residue" of the cake will be in a different state than the rest of the cake. In our example, that residue is, 52*7 - 360 = 4 degrees. So 4^o worth of cake will be frosting-side up, rest will be frosting side down. Note that the residue is always lesser than the value of 'd'. If we repeat this process once more around the cake, the residue will increase to 8^o.. So, taking d = 7^o and going around the cake once (52 times), is as if we started with d = 4^o and did the operation once. The solution is then apparent, keep continuing until the "residue" flips the whole cake over. In this case, it will happen after 2*(360/4) rotations of the cake.

Of course, it is possible that the "residue" is not an factor of 360, For example, if d = 17, the residue left after one rotation is: 22*17-360 = 14 deg. But that is not a problem! Because the residue of the residue can be a factor of 360.

And since each "residue" is lesser than the value of 'd' (or the previous residue), the process needs to converge.

In other words, the cake will be flipped over eventually, for all integral values of 'd'.

For rationals expressed as p/q (with p and q being co-prime), performing the operation 'q' times is the same as performing the operation once with d = p. So the cake will be flipped for all rational 'd' as well.

It remains to prove that all irrational values of 'd' can't "flip" the cake over. This can also be shown... approach can be similar..

Karthick,

I hope you haven't given up. Although your proof made the mistake that plasmid's proof successfully avoided, it may be easier for you to correct your reasoning than it is for plasmid. In that respect, you may actually be closer to finding a solution with your "residue" argument.

Don't give up!

[bonanova]

Now I know that old age has caught up with me.

The reason I had thought this one through a while ago is that in 2009.

And now that I've re-read it, I understand the key thought.

 

[gavinksong]

Now I know that old age has caught up with me.

The reason I had thought this one through a while ago is that in 2009.

And now that I've re-read it, I understand the key thought.

Hahaha. I can't believe it! You even showed us the image that you made for the explanation of the problem. ... Did you think of this problem yourself, bonanova?

I apologize for reposting an old puzzle.

It seems that Professor Templeton's answer is actually only half right... So perhaps it is good that this problem has been revisited.

Come on, guys. All the ideas that have been proposed so far (By karthick and plasmid) are valuable. Just put them together.

[bonanova]

No problem revisiting old problems, as far as I am concerned, although generally it's not desirable. For all practical purposes there is a new set of Denizens solving problems these days, and, as I have proven, the remaining solvers may have forgotten the old problems. In most cases if they remember, they just keep quiet and watch.

 

No, it's not mine, and I don't know who to credit.

 

I got this from a book that I had back then, and can't find now. It's not from Martin Gardner, my past muse, but possibly from Peter Winckler. I searched for it to revisit the answer, but could not find it. Finally, the site search found my old posting of it. Thankfully, I explained it then in a way that I can understand now. A tribute, I guess, to my former clarity.

 

Also, it was not completely solved back then. Prof Templeton gave an example that semi-proved his answer, however, so I gave him credit.

[karthickgururaj]

I agree that my earlier attempt had a bit of "hand-waving"

 

So let me try to make it slightly more formal, perhaps that will help in revealing the error.. Slightly longish post

 

It is good to have a notation to refer the "state" of the cake. Starting from 0 deg, say the cake top is frosted for x0 deg, then cake bottom is frosted for x1 deg, etc, until 360 deg is reached.

 

Let us denote it by:

  Cake(F => (0, x0); F' => (x0, x1); F => (x1, x2); ... ; (F or F') => (x, 360))

(F stands for frosted side up, F' for frosted side down).

 

or even more briefly (though redundant, we retain 0 and 360 for clarity):

  C(F => 0; x0; x1; ..., xn; 360)

 

The initial state of the cake is: C(F => 0; 360), which we will refer to as 'S0'

 

A cake that is half-frosted can be represented as: C(F => 0; 180; 360). Note that C(F => 0; 90; 270; 360) is also half-frosted, but is considered different from C(F => 0; 180; 360)

 

Next we define a transformation on the cake t(c, d), that changes the cake state c to a new state c' by

  1. First cutting d degrees of cake (from 0 deg)

  2. Then flipping the cut part over

  3. And then rotating the cake by d degrees clockwise (so there is a "cut" at 0 degrees)

Note: We assume 0 < d < 360 here (we'll remove that assumption later..)

 

So, as an example

   t(S0, 60) = C(F' => 0; 60; 360)

   t(C(F' => 0; 60; 360), 60) = C(F' => 0; 120; 360)

 

We also define: t(t...t(t(c, d), d))..) to be tⁿ(c, d) - i.e, repeated applications of the transformation 'n' times.

 

So, as an example

   t⁶(S0, 60) = C(F' => 0; 360)

 

The puzzle can then be worded as: For what values of 'd', there exists an 'n' such that: tⁿ(S0, d) = S0

 

Ok, with the notation taken care of,

 

 

We assert that (without proving) that:

Lemma 1: If (d1+d2) < 360, then t(t(S0, d1), d2) = C(F' => 0; (d1+d2); 360)

 

If 'd' is a factor of 360, such that 360/d = m, then it follows that:

  t^m(S0, d) = C(F' => 0; 360) = A completely flipped over cake

And so,

  t^2m(S0, d) = S0

 

Result 1: So factors of 360 are possible values for 'd'.

 

We next look at other values for 'd' which are not factors of 360, but less than 360. Say, d = 61 deg (for instance). After each transformation, the cake will change as below:

   t(S0, 61) = C(F' => 0; 61; 360)

   t²(S0, 61) = C(F' => 0; 122; 360)

   t³(S0, 61) = C(F' => 0; 183; 360)

   t⁴(S0, 61) = C(F' => 0; 244; 360)

   t⁵(S0, 61) = C(F' => 0; 305; 360)

 

Applying the tranform once more will yield:

   t⁶(S0, 61) = C(F => 0; 6; 360)

 

Continuing further, we finally get:

   t¹²(S0, 61) = C(F' => 0; 12; 360)

 

But that is same transform as t(S0, 12). In general, if m*d is the smallest integral multiple of 'd' greater than 720, then:

   t^m(S0, d) = t(S0, (m*d-720))

 

(Ok, little bit of hand-waving there..)

 

Let us call (m*d - 720) = r as "residue" of d

If r > d, then it implies ((m-1)*d - 720) > 0, which is not possible (since m*d is the smallest multiple greater than 720).

 

So for every 'd' (that is not a factor of 360), we can find 'm' and 'r' such that:

   1. r < d

   2. t^m(S0, d) = t(S0, r)

 

If 'r' is a factor of 360, the problem is then solved, if not, we can replace 'd' with 'r' and continue. Eventually, within finite number of steps, the residue will become a factor of 360 (if not, it will finally become '1', which is a factor of 360).

 

Result 2: So any positive integer value of 'd' < 360 is acceptable

 

So far, the arguments are basically the same as earlier, no change yet..

 

Before looking at rational values of 'd', it is helpful to extend the transformation for values of 'd' greater than 360. To that end, let, d = d₁ + d₂ + .. d_n, where, d₁ < 360, d₂ < 360, .. d_n < 360 and d > 360. We define t(c, d) to be: t(t(t..t(c, d₁), d₂),.., d_n). For this definition to have any meaning, we must prove that, if d_a + d_b = d_c + d_d, then t(t(c, d_a), d_b) = t(t(c, d_c), d_d). This is not too difficult to prove, so we hand-wave

 

 

Now, continuing with rational values of 'd', where d = p/q (p and q being co-prime integers)

   t^q(S0, d) = t(S0, q*d) = t(S0, p)

 

Since 'p' is an integer, we will be able to reach the initial state S0 with rational numbers too.

 

Result 3: Any rational value of 'd' works too

 

Enough typing for today, I'll come back tomorrow Also, I have a sneaking suspicion that someone will point out a mistake in what I have done so far

 

[bonanova]

@karthickgururaj. You did a lot of detailed work. Eventually the question to be answered concerns whether any real number will work. Your analysis can begin with the assumption that the angle is simply a real number, then see if there is a contradiction to the premise the cake will still be restored.