Algorithms are pervasive in modern society, and brain teaser puzzles are a great way to get more familiar with algorithmic thinking! In this article, we will pose a deceptively simple problem about flipping pancakes and walkthrough the process of constructing a formal proof. For fans of algorithms, proofs, and breakfast-themed mathematics problems. 🥞
Picture the above, but stacked 100 pancakes tall!
You have a spatula and 100 blueberry pancakes. Each pancake is assigned a number corresponding to the number of blueberries it contains. For example: pancake 1, which we denote as P1, has one blueberry, P2 has two blueberries, and so on. These pancakes are in a stack and ordered randomly.
Flipping rule. If you repeatedly flip the top pancakes where is the number of blueberries in the top pancake (i.e., pick up the first pancakes, reverse them, and set them down), can you prove the following:
Given any pancake order, if you repeatedly flip the top pancakes according to our flipping rule above, the pancake with one blueberry will eventually appear on the top of the stack.
Hint: this will work for other numbers of pancakes besides 100, specifically any integer number greater than 1.
A good place to start when proving something is to work through small versions of the problem by hand to gain intuition about what is going on.
Let’s say that instead of 100 blueberry pancakes, we have five blueberry pancakes (again in some random order). What happens if you apply the process described in the problem above? Click the “Flip the pancakes!” button to flip once. Keep clicking and follow P1.
You have flipped 0 times.
Nice flipping! You may have noticed that P1 will rise to the top pretty quickly and then get stuck there. If you repeat this a few times (click “New batch” to randomize the stack), we also see that, sometimes, all the pancakes will end up sorted. This doesn’t happen every time, but it does happen often enough to make one curious. Something about the flipping process wants to sort the pancakes.
To dig further into this, we can enumerate the configurations in which the stack ends up sorted (at least for five pancakes!). For this to happen, the last flip must move P1 to the top, and keep all other pancakes in sorted order—it turns out that there are only four cases where this can happen.
The following tree structure shows the final sorted configuration at the root: ″5,4,3,2,1″. Beneath, it shows all the configurations that could lead to that outcome as children. Here, the bottom of the stack of pancakes is the leftmost number in the list, while the top of the stack is the rightmost number. For example: in ″3,2,4,1,5″, P3 is on the bottom and P5 is on top.
Notice that in three out of the four configurations, P5 is at the bottom of the stack already, and in the case that it is not at the bottom, it must be moved to the bottom!
Now, what happens if we expand our previous tree structure a level deeper:
If you have pen and paper, try to expand one more level and notice what happens.
Aside. Notice that ″5,4,3,2,1″ is not the only final configuration in which the P1 finishes on top!
It is possible to reach many other final configurations where P1 is at the top of the stack; however, these will not be sorted stacks.
For example, consider the boring configurations where P1 is initially on top: no flips are needed, but the remaining pancakes could be in any of remaining different configurations.
For completeness, and for those without pen and paper, below is the complete tree of all configurations that lead to the sorted end configuration of ″5,4,3,2,1″! We’ve included Python code to reproduce this and encourage further exploration at the end of the article.
Click on configurations to expand them to see the sequence of configurations that lead to having the stack of pancakes in sorted order.
Hopefully after working through the example above you are convinced that the original problem statement is likely true. Using the observations gained from the exercise above, we will now formally prove that P1 will always come out on top!
As hinted in the previous section, the proof relies on the observation that once you flip the largest pancake in the stack you cannot move it again.
Proof. Consider a stack of sequentially numbered blueberry pancakes in some random order.
First, observe that if the largest pancake, pancake , in the stack is flipped, then it can never be moved again. For example, without loss of generality, let . Now, if pancake 100 is on top of the stack and is flipped, then it will move to the bottom of the stack. In order to move this pancake again, there would need to be a pancake with more than 100 blueberries in the stack, but we already said , so this cannot be done.
The proof continues as follows:
If you’re still craving more, there is an impressive body of technical work dealing with pancakes—flipping, sorting, and even burning pancakes! Mathematicians get hungry too. Interested readers should check out the relevant Wikipedia page.
Below you’ll find the Python code that we used to generate the trees above.
def inverse_flip(node, i):
'''Given a node and an index, return the node
that results from having previously flipped node[i]'''
return node[:i] + node[i+1:][::-1] + [node[i]]
def expand(node, indent="", current_depth=0, print_tree=False):
'''Recursive method for printing out all configurations
that lead to a given node. Returns the largest depth reached
by a child node.'''
if print_tree:
print(indent, current_depth,node)
largest_depth = current_depth
for i in range(len(node) - 1):
if i + node[i] == len(node): # we can do a flip
new_node = inverse_flip(node, i)
# recurse and keep track of the deepest child node
t_largest_depth = expand(
new_node,
indent + " ",
current_depth + 1,
print_tree = print_tree
)
largest_depth = max(
largest_depth,
t_largest_depth
)
return largest_depth
For example, we can use:
expand([5,4,3,2,1], print_tree=True)
to print the tree from earlier in the article. The numbers before each stack indicate its depth in the tree.
0 [5, 4, 3, 2, 1]
1 [1, 2, 3, 4, 5]
2 [1, 2, 5, 4, 3]
1 [5, 1, 2, 3, 4]
2 [4, 3, 2, 1, 5]
1 [5, 4, 1, 2, 3]
2 [3, 2, 1, 4, 5]
2 [5, 3, 2, 1, 4]
3 [4, 1, 2, 3, 5]
2 [5, 4, 1, 3, 2]
3 [2, 3, 1, 4, 5]
3 [5, 2, 3, 1, 4]
4 [4, 1, 3, 2, 5]
5 [4, 1, 5, 2, 3]
6 [4, 1, 5, 3, 2]
5 [4, 1, 3, 5, 2]
6 [4, 1, 2, 5, 3]
4 [5, 2, 4, 1, 3]
5 [3, 1, 4, 2, 5]
6 [3, 1, 4, 5, 2]
1 [5, 4, 3, 1, 2]
2 [2, 1, 3, 4, 5]
3 [2, 1, 5, 4, 3]
2 [5, 2, 1, 3, 4]
3 [4, 3, 1, 2, 5]
4 [4, 3, 1, 5, 2]
2 [5, 4, 2, 1, 3]
3 [3, 1, 2, 4, 5]
3 [5, 3, 1, 2, 4]
4 [4, 2, 1, 3, 5]
4 [5, 3, 1, 4, 2]
5 [2, 4, 1, 3, 5]
6 [2, 5, 3, 1, 4]
7 [2, 5, 4, 1, 3]
From this we see that the longest possible path to ″5,4,3,2,1″ takes 7 flips starting from ″2,5,4,1,3″. In fact, this is the longest path considering any final configuration using five pancakes, i.e., out of all possible final configurations using five pancakes, the greatest number of flips occurs when the final configuration is sorted.
To conclude, we will leave you with a question: Is it the case for every , that the longest path from an initial configuration to a final configuration must be when the final configuration is in a sorted order? In other words, what is the worst case number of flips that can happen for pancakes?