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?

[karthickgururaj]

One question: is it allowed to use infinite operations on the cake? I mean, let us say given a 'd' (any real number), if I can show that we can approach arbitrarily close to the initial cake "state" (i.e, all the frosting will be on top, except for an arbitrarily small section) - would that count?

 

Or, must it always become the cake with all frosting on top in finite amount of steps?

Edited October 26, 2014 by karthickgururaj

[gavinksong]

One question: is it allowed to use infinite operations on the cake? I mean, let us say given a 'd' (any real number), if I can show that we can approach arbitrarily close to the initial cake "state" (i.e, all the frosting will be on top, except for an arbitrarily small section) - would that count?

Or, must it always become the cake with all frosting on top in finite amount of steps?

Finite.

[karthickgururaj]

 

One question: is it allowed to use infinite operations on the cake? I mean, let us say given a 'd' (any real number), if I can show that we can approach arbitrarily close to the initial cake "state" (i.e, all the frosting will be on top, except for an arbitrarily small section) - would that count?

Or, must it always become the cake with all frosting on top in finite amount of steps?

Finite.

 

 

 Ok, I give up

[bonanova]

 

 

Finite.

 

 

 Ok, I give up

 

 

If it seems impossible (see my footnote) you're probably trying to solve the wrong problem.

Or perhaps thinking in terms that are too simple.

Make sure you're answering the question that the OP asks.

 

The OP asks about returning all the icing to the top;

It does not ask about turning over the same pieces twice.

It's manifestly obvious the same pieces will not even be encountered twice, if the cut does not divide 360^o.

 

Note that the first cut-and-flip moves the far edge of the cut piece to the zero-degree position.

And so for ever cut, which is especially important when a piece is cut that is part icing and part cake on top.

It's complicated to visualize, but it's the only way to see that it can happen.

[plasmid]

Denote the state of the cake as a set of numbers indicating the positions at which the cake transitions from being frosting-up to frosting-down, followed by the position of the cutter. For example, if the cake were frosting up from 0 to 70 degrees, frosting down from 70 to 190 degrees, and frosting up from 190 to 360 degrees (therefore with no up/down transition at the 360 degree point) and with the cutter sitting at 30 degrees about to make the next cut there, its state would be denoted {70, 190; 30}. I won't worry about distinguishing whether the first piece starts out frosting-up or frosting down, because if the cake ever reaches a state of being all frosting-down then it will eventually reach a state of being all frosting-up after you repeat the same number of steps again, so reaching a point where there are no transitions will ensure that the cake will eventually be all frosting-up again.

Initially the cake is all frosting-up, so the state is just the empty set with the cutter at 0 degrees: { ; 0}. After the first cut&flip, the state will be {0, d; d}. After the second cut&flip, if d < 180 then the state will be {0, 2d; 2d}. When you make a cut&flip that brings the cutter past 360, call it cut number n, the piece that gets cut will be from (n-1)d to nd with the first part of that piece frosting-up and the second part of that piece frosting-down, so after flipping you'll still have the first part of that flipped piece frosting-up and the second part frosting-down, but you will have changed the position of the transition point that was initially at 0 degrees. You will have gone from state {0, (n-1)d; (n-1)d} to state {x, (n-1)d; nd}... it's possible to solve for x (the new position of the transition point that was originally at 0), but for the moment I'll defer too much calculation. Now when you make the next cut, you'll introduce another transition at site nd and have {x, (n-1)d, nd, (n+1)d; (n+1)d}.


That explanation should give you a sense of how this process would work. Now consider in general how to take a state and calculate the new state that you will reach after making a slice and flipping. There will be cuts at position nd and (n+1)d. The flipping will do three possible things:

1) If there are an even number of transitions between nd and (n+1)d then the piece will initially have the same orientation at its edges (either both frosting up or both frosting down), and after flipping, both edges will have switched orientation. If there were not already transitions at nd or (n+1)d then transitions will be introduced there; if there were transitions at either nd or (n+1)d then those transitions would be destroyed.

2) If there are an odd number of transitions between nd and (n+1)d before flipping then the edges of the cut piece would be in opposite orientations before flipping, and after the piece gets flipped, the edges will be back in the orientation they were in before flipping. So there will not be a change in the number of transitions.

3) Regardless of which case of 1&2 we're dealing with, we know that any transition points between nd and (n+1)d will likely move, sort of like in the explanation earlier where the initial transition at 0 degrees moved to x degrees after the cutter made it completely around the circle. Now we'll solve for where a transition point would move to. If a transition point starts at position y and moves to position z, then y - nd (mod 360) = (n+1)d - z (mod 360), so z = (n+1)d + nd - y = (2n+1)d - y (mod 360).


Now consider the transition point that started at 0 degrees. When the cutter makes it around the cake, z = (2n+1)d - y (mod 360). Since y=0 for the transition starting at 0 degrees, and the cutter moved from just under 360 after cut n (with position nd) to just over 360 after cut n+1 (with position (n+1)d), we have z = (2n+1)d (mod 360) = (nd + (n+1)d) (mod 360). So we now have the cutter at position (n+1)d with the transition point moved to (nd + (n+1)d), which is of course nd degrees ahead of the cutter's current position, so it will be reached again in the near future (before one complete circuit around the cake). But if there is a transition within d degrees ahead of it then it will invoke process #2 before being reached and will not be destroyed (and there will be a transition within d of it after the transition at 0 gets flipped). This might be a good time to look at an example; I'll use d=90*sqrt(2) as the irrational cut size.

{0, 90*sqrt2 =~ 127; 90*sqrt2 =~ 127}
{0, 180*sqrt2 =~ 254; 180*sqrt2 =~ 254}
The next cut goes to 270*sqrt2 =~ 381, which crosses 0 degrees and moves that transition point, and has an odd number of transitions between the two cut points to invoke process #2 instead of #1, so we get
{180*sqrt2 =~ 254, (2n+1)d - y (mod 360) = 5*90*sqrt2 (mod 360) =~ 276; 270*sqrt2 (mod 360) =~ 21}
The next step flips a piece with no transitions at the cut points and no transitions between cut points, so two new transitions are made.
{180*sqrt2 =~ 254, 450*sqrt2 (mod 360) =~ 276, 270*sqrt2 (mod 360) =~ 21, 360*sqrt2 (mod 360) =~ 149; 360*sqrt2 (mod 360) =~ 149}
The next step places a slice at 450*sqrt2 (mod 360), which is the transition point that was originally at 0 before it started moving. But there is one transition in the middle of the slice (180*sqrt2 =~ 254), so the edges of the slice are in opposite orientations and don't get obliterated by the flipping, but the transition at (180*sqrt2 =~ 254) gets moved.
{(2n+1)d - y (mod 360) = 810*sqrt2 (mod 360) =~ 66, 450*sqrt2 (mod 360) ~276, 270*sqrt2 (mod 360) =~ 21, 360*sqrt2 (mod 360) =~ 149; 450*sqrt2 =~ 276}

 

And at this point it seems complex enough for me to not want to keep trying to work things out entirely by hand.

[karthickgururaj]

I read up the link to the earlier thread posted by bonanova. Now I'm feeling 

 

But I doubt if I could have stumbled on the key point.. I really must work with paper (with diagrams of cake cutting), instead of typing out responses. gavinksong had mentioned "it is flipped, not inverted", now I really understand that part.

 

@plasmid: if you do not want to give up, try cutting a real cake Or at the least, draw some realistic 3D diagrams of the cutting and flipping process.

[karthickgururaj]

A very interesting puzzle, however. 5 stars

[DejMar]

I hope I took the right slice of cake.

In bonanova's "Cut the cake and flip it too", it is noted by its solver, Prof. Templeton, that where 180 < d < 360, the cake is restored in 4 moves. This would also be true where the bounds are included, i.e., 180 <= d <= 360. In the discussion of this problem, one can note that the unknown angle could be any real number.

If the angle d is 0 <= d <= 180, n cuts will eventually occur to where the sum of the angles, D, will eventually accumulate to where 180 <= D <= 180. Thus, 4n cuts, or 4 cuts of D will restore the cake. The same will also be true if the cut > 360. Given that a negative angle is but the counterpart to the positive in direction, d can then be any value of the set reals.

I am not sure if it can extend into the set of imaginary or complex numbers, though.

I agree with karthickgururaj, nice puzzle.  (And, thanks to bonanova's puzzle, too.)

Edited November 1, 2014 by DejMar

[plasmid]

Now I don't feel so bad about resorting to writing a program.

Assuming this isn't buggy, which is sort of hit-or-miss, it seems like you can accumulate a ton of transitions before they start going away. And for the case of a (nearly irrational) slice size of 11.72347 degrees, it takes over eighteen hundred flips for the cake to remove all of its transitions. Glad I didn't try to work that out by hand.

 

Every angle I've tested so far eventually destroys all of the transitions (so reaches an all-up or all-down state), but I'm afraid it's not as enlightening as I'd hoped about the underlying process and providing an explanation on why it must eventually reach such a state.

 

See post #30 for an explanation of the logic behind this program.

Its output has two lines for every flip, the first line is the location of the transitions in terms of coefficients of slice size (since every transition will occur at some multiple of the slice size), and the second line shows the locations of the transitions in terms of degrees.

 

#!/usr/bin/perl
use strict;
use warnings;
 
use POSIX "fmod";
 
# The slice size (in degrees)
my $slicesize = 11.72347;
 
# The set of locations of all transitions
# Note that all transitions will be at positions
#   that are multiples of $slicesize
# The values in @transitions will be the
#   integer coefficient of $slicesize
my @transitions = ();
 
# Slicing position
# Also just the integer coefficient to $slicesize
my $slicepos = 0;
 
# Number of transitions within the next slice
my $slicetrans = 0;
 
 
 
# Convert an integer coefficient of a position (like
#   $slicepos or @transitions) into degrees
sub degrees {
  fmod($slicesize * $_[0], 360);
}
 
# Test whether a transition is within a cut piece
# If the slice does not cross 0 degrees then it just
#   tests if slice1 < transition < slice2
# If the slice does cross 0 degrees then it tests if 
#   either slice1 < transition or transition < slice2
sub inslice {
  my $slice1 = &degrees($_[0]);
  my $slice2 = &degrees($_[1]);
  my $trans = &degrees($_[2]);
  
  if ($slice1 < $slice2) {
    ($slice1 < $trans) && ($trans < $slice2);
  } else {
    ($slice1 < $trans) || ($trans < $slice2);
  }
}
 
# Determine where a transition point should be moved
#   when it is within a cut piece being flipped
# The value returned is an integer coefficient of
#   $slicesize, not degrees
sub movetrans {
  my $slice1 = $_[0];
  my $slice2 = $_[1];
  my $trans = $_[2];
  
  $slice1 + $slice2 - $trans;
}
 
# Given a slice position followed by the list of
#   transition points, see if the slice position is
#   already somewhere within the set of transition
#   points. Return its index if so, return -1 if not.
sub findslice {
  my @transarray = @_;
  my $slice = shift(@transarray);
  my $foundslice = -1;
  
  for (my $i=0; $i < @transarray; $i++) {
    if ($transarray[$i] == $slice) {
      $foundslice = $i;
    }
  }
  $foundslice;
}
 
 
##### Now for the main program #####
do {
  # Look for any transitions that will fall within
  #   the next slice, and move the transitions that
  #   are within the slice as you find them
  $slicetrans = 0;
  for my $trans (@transitions) {
    if (&inslice($slicepos, $slicepos+1, $trans)) {
      $trans = &movetrans($slicepos, $slicepos+1, $trans);
      $slicetrans++;
    }
  }
  
  # If there were an even number of transitions
  #   within the slice, then if there is already
  #   a transition at a slice position then it will
  #   be destroyed and if there is not already a
  #   transition at a slice position then one will
  #   be generated there
  if ($slicetrans % 2 == 0) {
    if (&findslice($slicepos, @transitions) > -1) {
      splice (@transitions,
             &findslice($slicepos, @transitions), 1);
    } else {
      push (@transitions, $slicepos);
    }
    
    if (&findslice($slicepos+1, @transitions) > -1) {
      splice (@transitions,
             &findslice($slicepos+1, @transitions), 1);
    } else {
      push (@transitions, $slicepos+1);
    }
  }
  
  # Print the current slice number and set of transitions
  print ("Slice number: $slicepos\n");
  print ("Transition points (coefficients): @transitions\n");
  print ("Transition points (degrees):");
  for my $trans (@transitions) {
    print (" ", &degrees($trans));
  }
  print ("\n\n");
  
  $slicepos++;
}while(@transitions);

[bonanova]

A very interesting puzzle, however. 5 stars

 

Give gavinksong a green up-arrow on his OP.

[DejMar]

If d is positive and 0 < d < 180, multiple slices will eventually accumulate to the larger D. This, of course, will not occur for the trivial case where d is 0.

Edited November 1, 2014 by DejMar

[plasmid]

If you were to make 2*N cuts of 91 degrees, would that give you the same outcome as making N cuts of 182 degrees? (Suppose N is 3 for example.)

Or are you saying something else?

[bonanova]

Comment from the sidelines: Great explanation by plasmid!

Which raises the question: Which takes longer: this puzzle, or ten games of Mafia?

[gavinksong]

I hope I took the right slice of cake.

In bonanova's "Cut the cake and flip it too", it is noted by its solver, Prof. Templeton, that where 180 < d < 360, the cake is restored in 4 moves. This would also be true where the bounds are included, i.e., 180 <= d <= 360. In the discussion of this problem, one can note that the unknown angle could be any real number.

If the angle d is 0 <= d <= 180, n cuts will eventually occur to where the sum of the angles, D, will eventually accumulate to where 180 <= D <= 180. Thus, 4n cuts, or 4 cuts of D will restore the cake. The same will also be true if the cut > 360. Given that a negative angle is but the counterpart to the positive in direction, d can then be any value of the set reals.

I am not sure if it can extend into the set of imaginary or complex numbers, though.

I agree with karthickgururaj, nice puzzle. (And, thanks to bonanova's puzzle, too.)

If you were to make 2*N cuts of 91 degrees, would that give you the same outcome as making N cuts of 182 degrees? (Suppose N is 3 for example.)

Or are you saying something else?

DejMar, your proof is incorrect for the same reason the answer to plasmid's question above is no. The result is correct however.

Congratulations to plasmid for finding the solution! I'm glad you didn't give up.

Here's the explanation from BWOC:

The frosting will eventually be all on the top of the cake for all angles! The key insight that you may have missed is that when you flip a slice, it not only moves frosting back and forth between the top and bottom of the slice, but also flips the slice from left to right!

Consider a d degree cut. Let d divide into 360 n times with remainder a. Let b=d-a. If a=0, then d divides 360, and the cake will return to normal after 2n flips. Otherwise, we will partition the cake into 2n+1 parts: n+1 “A wedges” of angle a degrees and n “B wedges” of angle b degrees. We will alternate between A and B wedges all the way around the circle. There will have to be two adjacent A wedges somewhere, and we will put the boundary between two adjacent A wedges at the cut at the beginning of the first slice of cake we will cut.

When we make the first cut, we swap the first A wedge and the first B wedge, and rotate so that those two edges are moved to the end of the circle. Now the cake is still divided into alternating A wedges and B wedges, with the two adjacent A edges at the start of the next cut!

We can look at the 4n+2 sides of wedges of the cake, and notice that every cut, flip, rotate move is a permutation on these 4n+2 sides of wedges. They will therefore all return to the original permutation after a finite number of steps. At which time, the cake will not only have all the frosting on the top, but be exactly the same as it started!

[DejMar]

I want to recant my earlier post. After further study, and seeing the fallacy of the given solution, there is no FINITE solution to irrational numbers. Only for rational numbers. Only with infinite transitions will the cake revert to its original state for irrational numbers.

Edited November 3, 2014 by DejMar

[karthickgururaj]

I want to recant my earlier post. After further study, and seeing the fallacy of the given solution, there is no FINITE solution to irrational numbers. Only for rational numbers. Only with infinite transitions will the cake revert to its original state for irrational numbers.

I thought so too... but it is not true.

..the number of steps is finite.

 

[DejMar]

QUOTE (from plasmid's 'proof')

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.
....
Also for completeness: this only proves that all transitions will eventually be eliminated, ...
END QUOTE

plasmid's proof only shows that all transitions will be eventually eliminated. No proof that the number of transitions is finite.
On the contrary, applying the definition of an irrational number, neither the slice points nor the transition points will align (in less than an infinite number of transitions and rotations).

To the question of whether d can include irrational numbers, the answer is yes -- after an infinite number of cut-flip-rotate processes. But, to the answer where d can include irrational numbers after a finite number of cut-flip-rotate process, the answer is no.

[plasmid]

I'm not sure if I'm misunderstanding the point about the slice points and transition points never aligning because d is irrational, but the whole crux of my argument was the surprising finding that: if you start cutting and flipping at 0 degrees and d degrees, then after making it around the circle once, the cutter will cut out that transition point at 0 degrees and flip it so that now instead of lying at 0 degrees it will lie at some integer N times d degrees ahead of the cutter's current position (where N*d < 360), and will be exactly at a slice position the next time the cutter makes it around the cake. The transition points must always be some integer (call it M) times d degrees in front of or behind the cutter, where |M*d|<360, so there are a finite number of possible transition points relative to the cutter's position.

But I think gavinksong's post with the explanation from BWOC is even more elegant and easier to envision.

Edited November 4, 2014 by plasmid

[gavinksong]

QUOTE (from plasmid's 'proof')

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.

....

Also for completeness: this only proves that all transitions will eventually be eliminated, ...

END QUOTE

plasmid's proof only shows that all transitions will be eventually eliminated. No proof that the number of transitions is finite.

On the contrary, applying the definition of an irrational number, neither the slice points nor the transition points will align (in less than an infinite number of transitions and rotations).

To the question of whether d can include irrational numbers, the answer is yes -- after an infinite number of cut-flip-rotate processes. But, to the answer where d can include irrational numbers after a finite number of cut-flip-rotate process, the answer is no.

I think you misunderstood. You can read plasmid's post above, but there are in fact a finite number of states because the slices

do eventually align. Suppose 360 // d = n. Whether d is irrational or not, after one cycle around the cake (e.g. after n cuts), the remainder will be flipped behind the next cut. Then, after another n cuts, the last cut will align with the cut right before the remainder slice, which gives us a finite number of states.

[DejMar]

The theory that "there are in fact a finite number of states because the slices do eventually align", can not be true. Such a statement implies that an irrational number is either even or odd, id est, rational.

A rational number can never be irrational.
No amount of rational units of a cycle will result in the alignment of a cut and a flipped cut where the cuts are of irrational measure. And, it is by definition that a number of cuts is a measured in the counting numbers, id est, natural numbers, a subset of the rational numbers.

On the other hand, when expressed in an infinite number of cycles, we are using neither rational nor irrational numbers. Infinity, itself, is not a number. It is used in the calculation of the convergence to some real value, or the divergence toward a unboundless value. After an infinite number of cycles of slices creating sections that become infinitesmally small, each of the top and bottom of the cake will both approach to a state of both being frosted and both being unfrosted. Id est, there must be a divergence toward an unboundless value, as the definition of the state of frosted is the opposite of the state of unfrosted. Thus, even after an infinite number of cycles, there is no solution for an irrational value.

[plasmid]

I'm not sure we're completely understanding each other, but here goes.

It's true that if the cutter makes a slice at X degrees then he will never land at X degrees again because the cut size is irrational. But the slice positions move when a piece of cake containing a previous slice gets cut out and flipped. So he doesn't need to land on X degrees, he needs to land on wherever the slice from X degrees will be moved to when it gets cut out and flipped.

After a cut is made at any arbitrary point X, the cutter will eventually make it around the cake and cut out a piece containing X and flip that point into a new position Y such that the next time around the cake the cutter will land on Y. Y is irrational, but it's equal to a rational number (an integer in fact) times the irrational slice size, so it will be reached in a finite number of cuts. It's possible to have two irrational numbers that are integer multiples of each other, such as sqrt(2) and sqrt(8), so that 2 cuts of size sqrt(2) would reach the point sqrt(8).

Edited November 6, 2014 by plasmid

[gavinksong]

I'm not sure we're completely understanding each other, but here goes.

It's true that if the cutter makes a slice at X degrees then he will never land at X degrees again because the cut size is irrational. But the slice positions move when a piece of cake containing a previous slice gets cut out and flipped. So he doesn't need to land on X degrees, he needs to land on wherever the slice from X degrees will be moved to when it gets cut out and flipped.

After a cut is made at any arbitrary point X, the cutter will eventually make it around the cake and cut out a piece containing X and flip that point into a new position Y such that the next time around the cake the cutter will land on Y. Y is irrational, but it's equal to a rational number (an integer in fact) times the irrational slice size, so it will be reached in a finite number of cuts. It's possible to have two irrational numbers that are integer multiples of each other, such as sqrt(2) and sqrt(8), so that 2 cuts of size sqrt(2) would reach the point sqrt(8).

Exactly.

DejMar, I think the point of confusion is that, as plasmid said, the cuts

move when you flip a slice that already has a cut in it.

After n = 360 // d cuts, if there is a remainder r = 360 - d * n, your "first cut" (i.e. the starting point or the cut made at 0 degrees) will be r degrees after your current location. However, after the next flip, the "first cut" will be r degrees behind your current location. Then obviously, after n more cuts, you will land on your "first" cut again.

[bonanova]

[spoiler='Demonstration for irrational case']Amazingly, everything is on the Web.

This guy used Mathematica to simulate the problem.

For 185 degrees, it takes 4 cuts.

For 1 radian (an irrational number) it takes 84 cuts.

Check it out.

[karthickgururaj]

[spoiler='Demonstration for irrational case']Amazingly, everything is on the Web.

This guy used Mathematica to simulate the problem.

For 185 degrees, it takes 4 cuts.

For 1 radian (an irrational number) it takes 84 cuts.

Check it out.

Thanks for the link! Upvoted

[DejMar]

Trying to solve this for an irrational number, I did find that it is possible for the edge of a slice to meet a transition point due to the transposition of the flipped piece. Though it still was not proof, as the example I was looking at did not eliminate the transition point- pair, but only moved it and an additional transition point-pair had been created, and could imagine that as one transition may be eliminated, but multiple transitions may be created. My opinion had changed to that it may be possible for the elimination of all transitions, but I still was searching for a proof whether that was to be always the case. I will check out the video, perhaps the answer is there.