Combinatorial Card Flip Game

You can prove the game terminates by induction. A $1$ card deck terminates immediately. Now assume we have proven that it terminates for all decks up to $n$. If we imagine playing a game with $n+1$ cards, if card $n+1$ comes to the top of the deck, it will go to be bottom and can never enter play again. We are then playing an $n$ card game, which we know terminates. If card $n+1$ never comes to the top of the deck, we will never see the card on the bottom of the deck, so we can pretend it isn't there, in which case we are again playing an $n$ card game. So the game always terminates.

Added: I believe that an upper bound for the maximum number of turns is one less than the Fibonacci numbers, $F(n)$ with the index offset by $1$. Let $G(n)$ be the maximum number of turns for $n$ cards. $G(1)=0$ as card $1$ is on top. $G(2)=1$ for order $2,1$. $G(3)=2$ for order $3,1,2$ To find the recurrence, you don't want $1$ on the bottom or you will get it as soon as you find card $n$. So you are playing an $n-2$ card game which ends when you find card $n$ and haven't found card $1$. You play $1$ turn to put card $n$ on the bottom, then play an $n-1$ card game. So the recurrence is $G(n)=1+G(n-1)+G(n-2)$ To prove it by induction, note $G(1)=F(2)-1, G(2)=F(3)-1$ and assume we have proved it up to $n-1$, then $ G(n)=1+G(n-1)+G(n-2)=1+(F(n)-1)+(F(n-1)-1)=F(n+1)-1$

However, this assumes that you can play the $n-1$ card game avoiding $1$ for as many turns as an $n-2$ card game. For $4$ cards this works with the order $2413$ taking $4$ moves, and for $5$ it also works with $31452$ taking $7$. But for $6$ cards it fails. The way to find these is take the maximum series for $n-1$, put card $n$ on the bottom and work backwards. For $6$ you get stuck and $456213$ takes only $10$ turns. I haven't proven that there are no $11$ move decks.

As Arturo Magidin pointed out, my induction in the last answer doesn't hold, so here is a proof of termination. There are a finite number of orders of $n$ cards without $1$ on top, specifically $n!-(n-1)!.$ If the game does not terminate, we must have a loop that comes back to a previously seen order. Consider $m$, the largest card seen in the course of playing through the loop. After we see it, it goes to position $m$ and no other card in the loop can retrieve it, and we will never see $m$ again. Therefore there is no loop.