0
$\begingroup$

Suppose you have a stack of $n$ cards numbered $1$ to $n$, arranged in some order. Consider the following operation on the stack : if the number at the top of the stack is $k$, the top $k$ cards are reversed. For example, if the stack contents from top to bottom are 4 5 1 2 6 3, one gets 2 1 5 4 6 3. Show that for every initial state of the stack, eventually the card numbered 1 reaches the top of the stack (and of course after that further operations don't change the state of the stack).

$\endgroup$
0
$\begingroup$

Here are two proofs:

Proof 1:

Let the number on the top of the stack after $k$ steps be $a_k$. Consider the infinite sequence $a_1, a_2, \ldots$ . At least one number must appear infinitely often; let $M$ be the largest such number. If $M = 1$ we are done, otherwise assume $M > 1$. Eventually the numbers which appear only finitely often no longer appear, and so if we go far enough in the sequence, we get a segment $M, b_1, \ldots, b_p, M$, where each $b_i$ is less than $M$. But this is impossible, since immediately after $M$ being on the top of the stack, $M$ is at position $M$ from the top, and for it to move from there, something larger must be at the top of the stack.

Proof 2:

Use induction. This holds when there is only $1$ card in the stack. Suppose it holds when there are $n-1$ cards. Consider a stack with $n$ cards. If the card labelled $n$ ever reaches the top or bottom of the stack, from then on it stays at the bottom and never moves from there. We can pretend it is not there, and the problem reduces to the $n-1$ case. Otherwise, it never reaches the top or bottom of the stack. Since it never reaches the top, the number of elements reversed is never $n$, and the card at the bottom of the stack stays there throughout. We can swap $n$ with the card at the bottom of the stack, and all the moves remain the same as neither of them reach the top of the stack, and so the number written on the card does not matter. We are back to the case where $n$ is at the bottom.

(This is from a discussion on a private forum.)

$\endgroup$
  • 1
    $\begingroup$ For proof 2, it took me some time to understand how "we can swap $n$ with the card at the bottom of the stack". I understand that as "the numbers on these two cards no longer matter". $\endgroup$ – peterwhy Jan 11 '14 at 9:26
  • $\begingroup$ Yup, that's it. Thanks, I edited the text to include this. $\endgroup$ – Prateek Jan 11 '14 at 9:28

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.