The Pancake Problem
Instilling problem-solving skills in students is an important step in their understanding of mathematics. The strategies provide a framework for investigation and critical analysis, essential for independent learning. With this in mind, I decided to introduce my class to a well-known mathematics challenge, the pancake problem.
It was morning and I was making final preparations in my classroom when the bell sounded, heralding a cacophony of sounds only an energetic group of students can muster. In the corridor, I heard approaching voices.
“Yum. What’s that smell?” a girl’s voice came through the general din. This was quickly followed by, “I think it’s coming from our room.”
The door opened and a wave of students entered, some giggling as they went to their seat.
Granted, the sight appeared ridiculous. I had donned an oversized chef’s hat, and the bottom of my overly long apron threatened to trip me if I dared to take a step forward. With my spatula, I deftly tossed a pancake, holding a small pan over an electric cooker.
Several plates on the table were stacked with pancakes I had made earlier.
“Hot pancakes for breakfast,” I said, passing the plates around. As my students munched on pancakes, I commenced my lesson.
“Today we will look at a classic problem involving recursion,” I revealed. “It is called the Pancake Problem, which Microsoft’s Bill Gates had a part in developing when he was a college student.” This information piqued interest.
“In the normal course of events,” I began, “each pancake in a batch, like the one you are eating now, is pretty much uniform in size. Let’s see what happens when this is not the case.”
I reached behind the desk and held up a plate with pancakes of different size, stacked pyramid style.
“It’s the Tower of Hanoi problem,” Jimmy called out.
“No, Jimmy,” I replied. “But you’re right in the sense that both the Tower of Hanoi problem and the Pancake Problem involve recursion.”
“So, what exactly is the Pancake Problem?” Jimmy asked, wiping his fingers on his jumper after placing the last piece of pancake into his mouth.
I introduced the problem. “The aim is to find a methodical way to rearrange a randomly ordered stack of pancakes -some or all of which may be of different size- so that they end up from smallest to largest, like the pancakes I am holding.”
“That’s easy,” Elaine commented. “Rearrange the pancakes on the table and stack them in the same order.”
“It’s not that simple,” I replied with a smile. “Every challenge has its rules. The approach you must use is what I call ‘pick and flip’.”
Waving at the stack of pancakes on the plate, I continued.
“First, pick the pancake that you want to be at the top of the stack. Then all pancakes from the one you’ve chosen up to the top of the stack are flipped as one pile.”
I demonstrated this by placing the spatula between two pancakes, lifting the top pile and swiftly flipping the pile back onto the pancakes that were still on the plate.
“This brings the pancake you’ve chosen to the top,” I reminded them.
“Sir, where’s the recursion in flipping?” Jonah asked.
“You flip again to take the top pancake to where you want it to be, repeating the procedure until all pancakes are sorted,” I stated.
From the frown that followed, it seemed that Jonah and others were perplexed.
“But each time you will end up at where you were in the previous step,” Jonah protested.
“The stack for the second flip does not have to be the same as the first stack,” I tried to explain, somewhat unsuccessfully.
‘When all else fails, try PowerPoint’, I thought, quickly switching on the computer and seeing the first slide show on the projector screen.
“Here we have four pancakes of different size,” I began.
“The biggest one is number four, so the first step is move it to the top.”
“So, we flip 3, 2 and 4,” I said, pointing to the screen. “And what’s the next step?”
“Flip all of them to get number four to the bottom,” Jimmy answered proudly.
“Exactly, Jimmy. Number four will stay where it is. Now, find the next largest pancake and repeat the process.”
“The next largest is number 3, so we flip three and one,” Joyce informed the class confidently.
“Good. Number three is fixed in position. And then flip the pile consisting of pancake two, three and one,” I explained, using the next slide.
“And the last step is ….?” I asked, waiting for a response.
“Flip one and two,” several students called out simultaneously.
“Excellent,” I beamed at them. “For this combination, five steps were required.”
“Do you think it will always take five steps with four pancakes?” I asked.
“No,” Anna stated. “It depends on the order of the pancakes we start with.”
Other students nodded their head in silent agreement.
This response led to my next question.
“What is the smallest number of steps with four pancakes?”
“I know,” Jimmy answered. “Just one step. The pancakes are in reverse order, just like an upside down pyramid. Then flip all four pancakes,” he concluded.
Several students began clapping but were interrupted by Sue, who had raised her hand and began speaking.
“I think the minimum number of moves is zero,” she opined.
“Go on,” I encouraged her, sensing she was thinking clearly.
“Well, earlier you said the pancakes are randomly placed on top of each other. This means that it is possible that the four pancakes are in the correct sequence to begin with, so no reordering is necessary.”
I started to clap and was joined by others.
“Well done,” I said. “Now let’s investigate further. Using our ‘pick and flip’ method, is there a way of knowing in advance the maximum number of moves we might need?”
There was silence, broken by Adam.
“I’m not sure I understand what you’re saying, sir,” he announced, echoing the thoughts of other students.
“Okay,” I said, opening another PowerPoint presentation. “Look at this.”
“Here are combinations of four pancakes we can start with that require up to five steps to put in order. Is there any combination that will take more than 5 steps?” I asked hopefully.
“No,” Jimmy said, “because if there were, you’d have it on the screen.”
“Jimmy, if I had a stick of chalk I’d throw it at you,” I answered him, smiling.
To the class, now. “If you think there can’t be more than five steps, then we say that with a random stack of four pancakes, the upper bound is five steps.”
I allowed my students to muse on this point.
Janice made a thoughtful contribution.
“The upper bound is like an invisible wall we come across and can’t go through.”
“An excellent analogy, Janice,” I replied. “I’m informing all of you that the upper bound for four pancakes is, indeed, five steps.”
“Is there some sort of formula?” Adam asked, wanting to come to the heart of the problem.
“Yep,” I replied, showing the class another slide.
“Here are the upper bounds for two up to ten pancakes and their start random order.”
“Why not start with one pancake?” Jimmy asked.
“Because if there’s only one, it doesn’t need flipping at all!” Janice reminded him.
My students looked at the projector intently, trying to make sense of the data.
“How did you know what the stack has to look like at the start?” someone asked, taking the lesson in another direction.
“Computer simulation,” I replied. Blank faces meant I should elaborate.
“I used a computer program that completed the task thousands of times and recorded the number of flips. The maximum flip was the upper bound.”
This information impressed them.
“Perhaps a graph will help with finding a relationship between the number of pancakes and the upper bound,” I suggested.
“Does anything stand out from this?” I prompted.
‘The number of steps goes up by two each time,’ and ‘the upper bounds are odd numbers’ were two observations put forward.
“All that is true,” I agreed. “So do you think the upper bound for 11 pancakes is 17 + 2 = 19?”
The class was in general agreement that this was the case.
“True, the upper bound will be 19. Now, can you come up with a rule that connects the number of pancakes with the upper bound?” I asked, looking across the sea of faces.
“You double and subtract three to get the next upper bound,” Tao accurately observed.
The others now realised this, too.
“Spot on, Tao. We can write as a formula, upper bound = 2 x number of pancakes – 3,” I added.
The class seemed satisfied and thought this a good finish.
Better estimates for lower bound and upper bound
“But there’s more,” I revealed.
“In 1979, Bill Gates and a colleague used some quite complicated mathematics to show that an upper bound is (5*number of pancakes + five)/3. Let’s compare this with our rule upper bound = 2 x number of pancakes – 3,” I stated, switching to the next slide.
“They’re both upper bounds for the same thing but they’re not the same,” Jimmy commented, slightly concerned about the apparent inconsistency.
“That is because different methods are used,” I said, knowing clarification was required.
“Bill Gate’s estimate is the more accurate of the two, but, in fact, a better estimate of 18 x number of pancakes / 11 was found in 2009.”
I pointed to a part of the graph.
“From the graph, the point of intersection is 14 on the horizontal axis. This means that both estimates for the upper bound give the same value of 25 for fourteen pancakes.”
“And what does the rest of the graph show?” Tao enquired.
I pointed to the graph on the whiteboard as I explained.
“For less than fourteen pancakes, our estimate is lower than Bill Gate’s formula, hence it is more accurate. For more than fourteen pancakes, Bill Gate’s upper bound is lower, and hence, it is better than ours.”
The bell for the end of the lesson was not far away, so I had to conclude the analysis.
“Furthermore, since 2009, the best estimate we have is 18 x number of pancakes/11.”
I turned off the projector and picked up the spatula.
“Okay, we’ve talked enough about pancakes. Now let’s make some more,” I said, beckoning students to the front.