wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Reversish Card Shuffling
        
(Message started by: william wu on Nov 8^th, 2006, 2:05pm)

Title: Reversish Card Shuffling
Post by william wu on Nov 8^th, 2006, 2:05pm

The n cards of a deck are labeled 1 through n. We shuffle the deck as follows: if the card on top is labeled k, reverse the order of the first k cards. Prove that eventually the first card will be a 1, regardless of the deck's initial order.

Source: Ravi Vakil

Title: Re: Reversish Card Shuffling
Post by Whiskey Tango Foxtrot on Nov 8^th, 2006, 5:03pm

Whoa, it's wu himself! Well, this riddle doesn't seem like it should be in the hard section to me, but maybe I'm wrong. It is quite amazing if you can visualize it, though.

The end of the game is obvious, as the only way to stop shuffling cards is to have the 1 on top. Then only the top card is "shuffled." As this is a fun, but somewhat easy puzzle to work out, I won't post the complete solution here. I will post a general idea, though.

[hide]The trick is to notice that the arrangement algorithm gradually places the cards in reverse numerical order. Eventually, the n-valued card will be drawn and when the order reverses, the 1 will be on top.[/hide]

Title: Re: Reversish Card Shuffling
Post by towr on Nov 9^th, 2006, 12:35am

[hide]The states with 1 one top are the only stable ones.
If K is on top it will be out of reach after the next turn unless there is a higher card among the first K cards. If a higher card turns up, then new cards will be added to the first K.
So that's almost enough to say that there aren't any cycles, except in the endstate. And thus you must reach that end state.[/hide]

Title: Re: Reversish Card Shuffling
Post by Grimbal on Nov 9^th, 2006, 4:42am

I'd put it like this
[hide]If the shuffling doesn't stop, the number of states being finite, it is bound to end in a cycle.
Let's call M the highest card seen in the cycle. M>1 if it doesn't stop. At some time M is seen and sent to position M. The other moves reverse fewer cards, so they don't affect card M. So, there is no way for card M to return to the top.
[/hide]

Title: Re: Reversish Card Shuffling
Post by Grimbal on Nov 9^th, 2006, 7:52am

Much more difficult: (and I don't have the answer). For a stack of N cards,
- what is the maximum number of moves before reaching 1 on top?
- how many different states actually end with the stack completely ordered?

Title: Re: Reversish Card Shuffling
Post by towr on Nov 9^th, 2006, 9:27am

on 11/09/06 at 07:52:00, Grimbal wrote:

N #o max
1 1 1 0
2 2 2 1
3 5 2
4 12 4

It's a bit much to do the others by hand..

[edit]
5 34 7
6 108 10
7 407 16
8 1867 22
9 9718 30
10 62200 38
[/edit]

Title: Re: Reversish Card Shuffling
Post by jollytall on Nov 9^th, 2006, 10:13am

N=3 max =3 if the last non changing move is also counted, or to me more logically for N=1, max=0, N=2, max=1 and N=3, max=2.

Title: Re: Reversish Card Shuffling
Post by Sameer on Nov 9^th, 2006, 10:24am

intuitively, I feel this should have a mathematical formula behind it... for the original as well as Grimbal's variation. I don't think I am qualified to get it, maybe someone can try a hand at it...

Title: Re: Reversish Card Shuffling
Post by towr on Nov 9^th, 2006, 10:33am

on 11/09/06 at 10:13:20, jollytall wrote:

N=3 max =3 if the last non changing move is also counted, or to me more logically for N=1, max=0, N=2, max=1 and N=3, max=2.

Yeah, I don't know why I did that..

Anyway, http://www.research.att.com/~njas/sequences/A000375
No mathematical formula is given, so it'd be a nice surprise if we could find one.

Title: Re: Reversish Card Shuffling
Post by Eigenray on Nov 9^th, 2006, 12:38pm

To each configuration of the deck, associate [hide]an n-digit binary number, whose i-th digit is 1 iff card i is in position i. If card k != 1 is on top, then reversing the top k cards increases this number by at least
2^k-1 - (0+2¹+...+2^k-2) = 2.[/hide]
Hence there can be no more than 2^n-1 moves before reaching a fixed point, which clearly has a 1 on top.

Note that this same argument works no matter how the other (k-1) cards are permuted, as long as card k, in position 1, ends up in position k, and the cards in positions [2,k] end up in positions [1,k-1].

Title: Re: Reversish Card Shuffling
Post by Sameer on Nov 9^th, 2006, 2:17pm

Looks like this is the actual source of the original problem

http://links.jstor.org/sici?sici=0036-1445(197710)19%3A4%3C739%3AP7%3E2.0.CO%3B2-P