0
$\begingroup$

Given n pancakes, for each permutation we can compute the minimum number of pancake flips. If we take the maximum over all possible permutations, we get the worst case pancake number $P_n$.

I think I can prove that $P_n \geq n$. My argument is that I can start from the sorted pancake, and do a "anti-sorting" of the pancake by first flipping at position n, then position at n-1, n-2, etc.

For example, the case of n=5 would yield 34251.

Sorting such a pancake would take at best n steps.

Am I doing something wrong?

$\endgroup$
  • 1
    $\begingroup$ "Pancake flips"? It sounds like you are omitting part of the homework exercise. $\endgroup$ – MSalters Apr 25 '17 at 6:57
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Apr 25 '17 at 7:04
  • $\begingroup$ Pancaked? Permutations? Flips? What are you talking about? $\endgroup$ – David Richerby Apr 25 '17 at 8:32
  • 1
    $\begingroup$ While this is a somewhat-familiar problem, as you've seen there are still some (many, I'd guess) who have no idea what's going on here. Perhaps you could explain ("you have a stack of flat cakes and a spatula and can insert the spatula between two cakes in the stack ...") a bit more. $\endgroup$ – Rick Decker Apr 25 '17 at 12:45
2
$\begingroup$

I assume that you are talking about the Pancake sorting (wiki) problem. Your argument for $P_n \ge n$ is rather informal.

The paper "Bounds for Sorting by Prefix Reversal (1979)" gives the lower bound $P_n \ge n$ in the Introduction section. Better lower bounds are also mentioned in this paper.

This paper "Pancake Flipping Is Hard" (2011) proves that determining the minimal number of moves for a given stack is NP-hard.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.