From this we gather that P 3
=3. Shall we try to calculate P 4
n 1 2 3 4 5 6 7 8 9
Pn
with the same strategy? If so how many arrangements would we need to try? All we need to do is find the factorial of 4, which is 24. This means we will have to go through 24 different ways to arrange 4 pancakes, then calculate the number of flips required for each scenario and take the largest number of flips required. Using n! we can find how many different way there are to arrange n pancakes. As can be imagined, the different arrangements necessary to find Pn soon gets out of hand. If there are 10 pancakes, there are 3,628,800 ways to arrange them, which is why computers have to be used to calculate Pn quickly. Here’s a table of the pancake numbers that we know of. No one has been able to calculate it for n=20. Despite having access to super computers, it is simply too big of a task to find the most amount of flips required. In order to understand how mathematicians obtain a maximum number flips, let’s look at how to create a formula to solve any stack. List notation will be necessary. The correct order for 4 pancakes (which we shall call x) is {a,b,c,d}. A permutation is a different way things can be ordered, so a permutation of x can be {c,b,d,a}.
0 1 3 4 5 6 8 9
10 11
10
n
Pn 13 14 15 16 17 18 19 20 22
11 12 13 14 15 16 17 18 19 20
?
If there is the stack of pancakes, x, that looks like {b,c,a,d}, that means the second smallest pancake is on the top, followed by the third smallest in the second position. The smallest pancake would be in third position. We express the pancake in the fourth position as x(4)=d, which would be the largest pancake... Now let’s sort this stack using the following steps.
1. Find the biggest entry in the current permutation that’s in the wrong place: let’s say it’s number in position .
2. Reverse the first entries, so that is now in position .
3. Reverse the first entries, so that the number is now correctly in position .
4. Go back to step and repeat, until the whole permutation is sorted.
We would find the biggest entry in the incorrect position (the largest pancake in the third position), and flip the number of pancakes equal to its position (since it is the third position, we flip the first three pancakes). This results in {d,b,c,a}. We now flip the number of pancakes equal to its size (largest out of four pancakes means flip top four pancakes). This gets us {a,c,b,d}. We repeat these steps to get {c,a,b,d}, then {b,a,c,d}, and finally {a,b,c,d}.
42
Made with FlippingBook - Online Brochure Maker