Pancake Numbers - Numberphile
video description
I can prove for a small n that the smallest number of flips is bounded by p(n) lets say n=3, p(n)=3.
Then for a list (unordered) of size k=n+1,
i can say that for (k-1! of the permutations, it will be ordered as follows; [1. n], k, which is solvable in p(n, then there is also (k-1! of the permutations ordered as follows k, [1. n], which can be fliped in at most p(n)+1 which leaves k! -2(k-1) permutations that are ordered as follows [a. b], k, [c. d], (a, b, c, d a partition of 1 to n) which can be fliped to k, [b. a], [c. d], and then fliped again to [d. c], [a. b], k which is (as above) solvable in at most p(n. so for any permutation of size k, it can be fliped in 2+p(k-1)
Which I think by induction means that the upper bound for p(n) = n+2. I and I think many other's with a similar logic would be interested to know why this is not the upper bound?
Date: 2022-04-08
Related videos
Comments and reviews: 9
kujmous
Would the problem be simpler if instead of n pancakes we saw it as (n-1) differences in sequential pancake sizes? The problem then becomes how do we maximize the number of ones, and if the number of ones cannot be increased, select the highest n that isn't already nth and select the flip that places it nth. Wait, that would be covered by the most-1s logic. Hmmmmm. We're never forced to select a gap of 1 or else they would all be in order (or possibly perfectly upside down. A flip can only change one difference at a time. Is it possible to always have a move that reduces a non-1 difference to 1? No.
Starting at n, if n is nth, it is now the plate. Never flip it again. It is no longer a pancake.
For any sequence of pancakes in consecutive order, they are now one pancake. Never separate them.
Select the move that reduces the number of pancakes, if it exists. Otherwise flip the remaining stack that is still considered pancakes.
reply
Would the problem be simpler if instead of n pancakes we saw it as (n-1) differences in sequential pancake sizes? The problem then becomes how do we maximize the number of ones, and if the number of ones cannot be increased, select the highest n that isn't already nth and select the flip that places it nth. Wait, that would be covered by the most-1s logic. Hmmmmm. We're never forced to select a gap of 1 or else they would all be in order (or possibly perfectly upside down. A flip can only change one difference at a time. Is it possible to always have a move that reduces a non-1 difference to 1? No.
Starting at n, if n is nth, it is now the plate. Never flip it again. It is no longer a pancake.
For any sequence of pancakes in consecutive order, they are now one pancake. Never separate them.
Select the move that reduces the number of pancakes, if it exists. Otherwise flip the remaining stack that is still considered pancakes.
reply
Will
Is there an upper bound on the increase between the pancake numbers that's better than 4. I think I proved that pancake(n+1)=> pancake(n) + 4. Here's my idea: . If you ignore the pancake which is on the bottom and solve for all the pancakes on top, and then insert the spatula where that pancake should be, flipping all the ones above it, then flipping all the pancakes but the one on the bottom, then flipping the whole stack, then flipping the stack from below the smallest, you have the ordered stack. It took, at maximum, the maximum number of flips required for one fewer pancake, plus 4.
reply
Is there an upper bound on the increase between the pancake numbers that's better than 4. I think I proved that pancake(n+1)=> pancake(n) + 4. Here's my idea: . If you ignore the pancake which is on the bottom and solve for all the pancakes on top, and then insert the spatula where that pancake should be, flipping all the ones above it, then flipping all the pancakes but the one on the bottom, then flipping the whole stack, then flipping the stack from below the smallest, you have the ordered stack. It took, at maximum, the maximum number of flips required for one fewer pancake, plus 4.
reply
Mennenth
man the past few numberphile videos have been kinda misses for me (except for the parkercircles, those were a hit. They've all been over complicating the issue or overlooking something crucial. This video mentioned a crucial point (its always possible to take no more than 2 flips to get the largest where it needs to go, but then dismissed it almost immediately without examining the consequences of it (for any n the upper bound cannot exceed the pancake number for n-1 by more than 2. which proves that 18n/11 is horribly wrong when it comes to trying to predict the upper bounds.
reply
man the past few numberphile videos have been kinda misses for me (except for the parkercircles, those were a hit. They've all been over complicating the issue or overlooking something crucial. This video mentioned a crucial point (its always possible to take no more than 2 flips to get the largest where it needs to go, but then dismissed it almost immediately without examining the consequences of it (for any n the upper bound cannot exceed the pancake number for n-1 by more than 2. which proves that 18n/11 is horribly wrong when it comes to trying to predict the upper bounds.
reply
john
If the pancake number for 19 pancakes is 22, then the upper bound for 20 pancakes is 22+2, 24.
Proof: Take any stack of 20 pancakes and flip the biggest pancake along with everything on top of it so that the biggest pancake is on top. Next flip the whole stack so that the biggest pancake is on the bottom and had 19 randomly arranged pancakes on top of it. Proceed to solve the 19 remaining pancakes without touching the largest one on the bottom using a maximum of 22 more moves.
This proof can be expanded to show that any stack can be solved in 2n-16 moves.
reply
If the pancake number for 19 pancakes is 22, then the upper bound for 20 pancakes is 22+2, 24.
Proof: Take any stack of 20 pancakes and flip the biggest pancake along with everything on top of it so that the biggest pancake is on top. Next flip the whole stack so that the biggest pancake is on the bottom and had 19 randomly arranged pancakes on top of it. Proceed to solve the 19 remaining pancakes without touching the largest one on the bottom using a maximum of 22 more moves.
This proof can be expanded to show that any stack can be solved in 2n-16 moves.
reply
Huug
Wouldnt you AT MOST add 2 flips for each added pancake?
Given you add a larger pancake anywhere in the stack, it would take 1 flip to put it on the top. One more flip to put it on the bottom. After that, you have a set of n-1, which is known.
Obviously there may be more efficient methods, but a top of 35 moves for a stack of 20 seems so much higher than the 22 for a stack of 19 that it makes no sense to me at all.
reply
Wouldnt you AT MOST add 2 flips for each added pancake?
Given you add a larger pancake anywhere in the stack, it would take 1 flip to put it on the top. One more flip to put it on the bottom. After that, you have a set of n-1, which is known.
Obviously there may be more efficient methods, but a top of 35 moves for a stack of 20 seems so much higher than the 22 for a stack of 19 that it makes no sense to me at all.
reply
ShotgunLlama
If I'm not mistaken, an upper limit for -burnt pancake numbers- would be 3n - 2, as each out of place or upside down item can be brought to the top(1, flipped if necessary(2, then returned to its appropriate place(3. And of course, for the final item, it would at most only need to be flipped, thus the -2. There might be a better bound than this, but this should be true.
reply
If I'm not mistaken, an upper limit for -burnt pancake numbers- would be 3n - 2, as each out of place or upside down item can be brought to the top(1, flipped if necessary(2, then returned to its appropriate place(3. And of course, for the final item, it would at most only need to be flipped, thus the -2. There might be a better bound than this, but this should be true.
reply
Cheeseburger
ARE THOSE FELT PANCAKES?
how to find number of possible combinations with pancakes
# of pancakes has #! combinations
exclamation mark = factorial sign in case you didnt know
ex: 10 pancakes has 10! combinations (3. 6288 x 10-6 combinations or 3628800 combinations)
wow thats a h--- of a lot combinations
reply
ARE THOSE FELT PANCAKES?
how to find number of possible combinations with pancakes
# of pancakes has #! combinations
exclamation mark = factorial sign in case you didnt know
ex: 10 pancakes has 10! combinations (3. 6288 x 10-6 combinations or 3628800 combinations)
wow thats a h--- of a lot combinations
reply
Lakshay
Wait what if pancake(19)=22 shouldn't the upper bound for pancake(20) be 22+2=24 coz it only takes 2 flips to turn an n pancakes situation into an n-1 pancake situation by first flipping to bring the biggest pancake on top then flipping the whole pile? What am I missing why is the upper bound taken as 35 or as 29 what
reply
Wait what if pancake(19)=22 shouldn't the upper bound for pancake(20) be 22+2=24 coz it only takes 2 flips to turn an n pancakes situation into an n-1 pancake situation by first flipping to bring the biggest pancake on top then flipping the whole pile? What am I missing why is the upper bound taken as 35 or as 29 what
reply
Michael
The pancake number any number can only be bigger by 2 than the one for n-1 since you could do the trick of flipping the biggest to the top and then to the bottom and then start with the optimised way for n-1. So what I am saying is that the upper bound for 20 pancakes mentioned at 4: 13 shouldn't be 35 but 24.
reply
The pancake number any number can only be bigger by 2 than the one for n-1 since you could do the trick of flipping the biggest to the top and then to the bottom and then start with the optimised way for n-1. So what I am saying is that the upper bound for 20 pancakes mentioned at 4: 13 shouldn't be 35 but 24.
reply
Add a review, comment
Other channel videos
