The pancake problem is really a coin-flipping problem. Basically, you start with a stack of coins all heads up. Then, you invert the first, invert the top two, invert the top three, . . ., invert the whole stack, invert the first, etc. until they are all heads up again. The problem is how many inversions does it take to thus right n coins?

This is the layman's way to solve for a given n (and by layman, I mean someone with a passing grade in linear algebra). I will someday come back and add why this works, and maybe even go about writing the proof for the weird part.

Solution for n coins:

Step one: Generate an nxn transformation matrix. It is a matrix whose columns form an orthogonal basis for real n-space, is invertible, and is generated in the following fashion:

1) start in the top right corner with a negative one.
2) move down one row and two columns to the left filling in negative ones as you go, until you go off the left edge of the matrix
3) find the first row and the first column that do not yet have a value and place a one there
4) move down one row and two columns to the right filling in ones until every row and column has exactly one number in it
5) fill in the rest with zeroes.

The following program will generate the matrix for you on a TI-89:

:coinmat(n)
:Func
:Local a,c,out
:newMat(n,n)->out
:1->c
:For a,n,1,-2
:-1->out[c,a]
:c+1->c
:EndFor
:For a,mod(n,2)+1,n,2
:1->out[c,a]
:c+1->c
:EndFor
:Return out
:EndFunc

I haven't proved that a matrix of this form will always result from the series of multiplications I used to generate it, but I'm 99% sure it works for arbitrarily large values of n.

Step two: Find the eigenvalues of the matrix.

Step three: Find the least integer x for each eigenvalue l such that l^x=1. (see note 2 below)

Step four: Find the least common multiple of all x's in step three. Call this value m.

Last step: If 1 is an eigenvalue of the matrix, use m*n is the number of inversions required. Otherwise, use (m*n)/2 is the number of inversions required.

Other Notes:

1) Because a matrix and its transpose have the same eigenvalues, it takes the same number of inversions if you start by inverting the whole stack, then invert the whole stack except the bottom, etc., as right-multiplying where I left-multiplied to get the transformation matrix will yield the transpose of the transformation matrix. As a result, you may use either the matrix as described above, or its transpose/inverse in this computation.

2) All of the eigenvalues of these matrices have a magnitude of 1 in the complex plane. Therefore, calculating the least power of any eigenvalue that yields 1 is as easy as finding the least multiple of the phase of the eigenvalue that yields a multiple of 2*pi. Actually, I have found two other ways to find this number. The simplest is just to count the number of unique eigenvalues, and double this if 1 is not an eigenvalue.

3) The ultimate goal in this problem would be to find a master function to give the minimum number of inversions for any number of coins n. It seems that first it would be best to find a function that will return all solutions for a given n, and will give the minimum number when you plug in 1 for a given variable. I suspect, for several reasons, that such a function will return the trivial solution of zero for n=1, and this is most probably the most useful thing for it to return anyway.

A Graphical Approach

Consider the above described transformation matrix as an adjacency matrix for a graph in which the non-zero entries define the weights for the edges (as I should have considered it from the beginning, since it tells where every coin will move to and what will happen to it after n inversions). For example, a 9x9 matrix would have a -1 at (1,9), therefore, the graph would have 9 vertices, with one edge with a weight of -1 going between vertex 1 and vertex 9.

The number m you are looking for, as above, is the length of the longest cycle, which, as it turns out, always contains the fourth from last vertex, second to last vertex, last vertex, and first vertex, usually connected one to the next in that order. (This last part about what vertices are contained is entirely conjecture, but it does make sense. At the very least, the first vertex is always contained.)

The product of the weights of the edges on this cycle tells how the number should be treated. If the product is -1, the number of inversions required is n*m-1. If it's 1, then use n*m.

Oddly enough, the factorization of the characteristic polynomial of the matrix completely describes all of the cycles in these graphs, as well as the state of the weights within the cycles.

As a result of this knowledge, I was able to write a program for the TI-89 that solved the number of flips required for 10000 coins (8,120,000) in 21 seconds. It also found correct numbers for the first 32 stacks in 28 seconds. It's still too labor-intensive for handwork, but it's one step closer to a solution. Thanks to Andrew Swerlick for getting me thinking along this line, however indirectly he did so.

Here is the program:

:ffflipn(n)
:Func
:Local a,c,w,cutoff
:floor((n+1)/2)->cutoff
:-1->w
:1->c
:n->a
:While a!=1
:If a>cutoff Then
:2*a-n-1->a
:Else
:-1*w->w
:n-2*a+2->a
:EndIf
:c+1->c
:EndWhile
:If w=-1 Then
:Return c*n-1
:Else
:Return c*n
:EndIf
:EndFunc