You have n cards, numbered 1 to n. Following operations are performed repeatitively:
Source: CSE_blog
- Choose the top most card. Say it is numbered i
- Reverse all the cards from 1 to i
This process stops when card #1 comes on the top. Prove that eventually the process stops
Source: CSE_blog
Solution by dheeraj Baba
ReplyDeleteConsider the permutation of cards. Say 1 never comes on the top
Claim 1: If a permutation repeat, then permutations will repeat in a cycle.
Pf: If a certain permutation repeats, then the same sequence of operations are performed repeatedly. Thus there is a cycle.
This means if there is no cycle of permutations, then no permutation will ever repeat and eventually we will get a permutation with one on top.
Claim2: There is no cycle of permutation
Pf: Say there is a cycle. Consider a permutation with card k on top. After the reversal, card #k goes to position k. For this permutation to repeat in the cycle, there must be a card numbered greater than k (say k+) in the permutation and it must come at the top as there is no other way for card #k to come back from its kth position. But as permutation starting with k+ is also in the cycle, there must be a card #k++ in the cards and it must come on top in some permutation. This means, even the highest numbered card lies in the cycle and must come on top repetitively. But, the highest card can come on top at most once. Thus, there is no cycle.
Just though that in the proof of claim 2 above, we should assume that K is the highest card on top in the cycle and prove that there has to be a card larger than K which is impossible hence destroying the claim of cycle.
ReplyDelete