**Source:**Asked to me by Nikhil Garg (Sophomore, IIT Delhi)

**Problem:**

We have a deck of n cards with cards labeled from 1 to n. Starting at any configuration , we repeat this : If the top card has number k , we reverse the order of top k cards. Prove eventually that 1 would be the top card.

I was able to solve it. Very interesting problem. :D

Update (03/01/10):

**Solution:**Posted by me in the comments!! Thanx to Giridhar and KP Ashwin (CSE, IITB) for the help.

Each time there will be a new card on the top of the deck.

ReplyDeleteHence at some point card no. 1 is inevitable at the top.

:)

@Taaki...

ReplyDeleteit is not true that a new card appears on the top with every reversal.

For example : 3, 5, 4, 2, 1

3 appears twice on top.

If we are able to show that each reversal results in a new permutation, then we can say it is inevitable( as there are only finite permutations possible ).

@Pratik Is this ur strategy ?

induction , my friend and all is done !!

ReplyDelete@Taaki: As pointed by giridhar, your solution is not correct!!

ReplyDelete@Giridhar: Yes that is my strategy. Thank You.

@KP: dude.. explanation. You thing all is well, but its not until you write it :P. BTW, Thanx. :) I was not able to find a "cool" solution until I saw your comment!

Solution:We can prove that each operation results in a completely new permutation.

This can be proved by induction.

This is of course true for base case k=2

Assume its true for k=n-1, i.e if there are n-1 numbers, then each operation results in a new permutation. To prove that this is true for k=n.

When there are n numbers, say the number at the bottom of the stack is n'. Now, we have 1 to n numbers excluding the number n' in the first n-1 numbers. Now each operation would result in a new permutation of n-1 numbers by the induction hypothesis. Until the number n comes to the top. Now the stack is inverted and n can never come to the top again. So, we are left the n-1 numbers again and each operation would result in a new permutation. Note the the two set of permutations are disjoint as in the first case, n' is always at the end. In the second case, n is always at the end.

So, each operation results in a new permutation. Since there are only n! (finite) permutation possible out of which (n-1)! (>=1) are "win" permutations, we will always reach a state when 1 is at the top.

Hope that is clear! Thanx Nikhil for the problem and Giridhar, KP for the hint.

I solved it also by induction,but without proving that it should cover all permutation.

ReplyDeleteNice problem btw

@Piyush.. Enlighten us with your solution :)

ReplyDeleteOne more induction bases solution:

ReplyDeleteInduct on the largest card that can come on top.

Base case: For any number of cards if 1 is the largest card that comes on top , 1 eventually comes at top ( as if !! )

IH : If Largest card that can come at top after any finite number of moves is less then n , We reach 1 at top in finite number of moves.

Proof: Assume it does not hold. Then this process does not terminate. Of all the possible cards at top , say n is the largest. After this step , n goes at bottom , and never is replaced again- no card greater then n comes at top ever. So by IH we take only finite moves from now onwards to get to 1 at top.

( I know it is little weird n extended )

@Nikhil.. Can you explain the solution?

ReplyDeleteYou seem to have mixed induction on number of cards and induction on the largest card on top. Define what n is in your induction hypothesis. What is the number of cards in the induction statement? (isn't it n?)

No . n is the largest number which comes at top. I am not even keeping a track of the number of cards in deck- that can be anything , I dont even want cards to be continuous in numbering or all cards to have finitely large numbers. I am just concerned with the largest card that comes on top.

ReplyDeleteIn the original problem , since the cards are from 1 to n, so largest card that comes at top is bound , so my proof establishes the desired there.

Claim 1: if in the initial pile the largest number is not at the last location then after a finite number of reversals it will be.

ReplyDeleteProof: Lets say N is the number of cards, Nth card is the largest. Lets say, ith card is on top. After 1st shuffling, i will be at the ith location in the deck. If N is not at the Nth location, then it will come at the top in one of 1-(N-1) reversals, and then it will settle at the bottom.

The same will continue for N-1 and so on. Eventually the whole deck should be sorted with 1 at the top.