Prove that this process always stops:?

Question

A deck of cards numbered 1 through n is randomly shuffled. Repeat the following process:
Take the top card, call the number on that card k. Reverse the order of the first k cards. Prove that this process will eventually stop with 1 at the top of the deck.

You're not actually throwing the cards out, so how do you know it will actually get to 1 rather than cycling?

The process stops when you hit 1. The question is why do you eventually hit 1 given any initial permutation?

Answer 1

Proof by contradiction:

Assume that it is possible to reach a steady state cycle other than the degenerate case of the single 1 card. Consider the cards involved in the cycle to be k_1, k_2, k_3, . . .k_q where q is the length of the cycle. Without loss of generality order the cycle so that k_1 > all other k in the cycle.

When k_1 is processed it will move to the k_1 position in the deck. all further flips will never involve k_1 as they will involve flips of size less than k_1 and k_1 exceeded the sizes of the other k's. As a result k_1 will never be moved out of the k_1 position in the deck, and therefore never moved into the first position. As a result we will never see the k_1 card again in the cycle. But this is a contradiction, hence our original assumption must be incorrect.

Answer 2

Well if you go through all the cards until eventually you come to 1 than it has to get there, unless you throw 1 away or something.

Answer 3

If the first card is 1, the process will stop. Thus the process will stop at 1.