Top Card
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.
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.
:)
Hi. No it's not necessarily correct. There are cases that same number can appear multiple times on the top before card number 1 appears.
DeleteExample: Consider 4 6 7 5 2 3 1 when 4 is the top card
@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.