Author |
Topic: Reversish Card Shuffling (Read 844 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Reversish Card Shuffling
« on: Nov 8th, 2006, 2:05pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Whiskey Tango Foxtrot
Uberpuzzler
Sorry Goose, it's time to buzz a tower.
Gender:
Posts: 1672
|
|
Re: Reversish Card Shuffling
« Reply #1 on: Nov 8th, 2006, 5:03pm » |
Quote Modify
|
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.
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.
|
|
IP Logged |
"I do not feel obliged to believe that the same God who has endowed us with sense, reason, and intellect has intended us to forgo their use." - Galileo Galilei
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Reversish Card Shuffling
« Reply #2 on: Nov 9th, 2006, 12:35am » |
Quote Modify
|
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.
|
| « Last Edit: Nov 9th, 2006, 12:36am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Reversish Card Shuffling
« Reply #3 on: Nov 9th, 2006, 4:42am » |
Quote Modify
|
I'd put it like this
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Reversish Card Shuffling
« Reply #4 on: Nov 9th, 2006, 7:52am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Reversish Card Shuffling
« Reply #5 on: Nov 9th, 2006, 9:27am » |
Quote Modify
|
on Nov 9th, 2006, 7:52am, Grimbal wrote: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? |
|
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]
|
| « Last Edit: Nov 9th, 2006, 10:34am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Reversish Card Shuffling
« Reply #6 on: Nov 9th, 2006, 10:13am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Reversish Card Shuffling
« Reply #7 on: Nov 9th, 2006, 10:24am » |
Quote Modify
|
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...
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Reversish Card Shuffling
« Reply #8 on: Nov 9th, 2006, 10:33am » |
Quote Modify
|
on Nov 9th, 2006, 10:13am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Reversish Card Shuffling
« Reply #9 on: Nov 9th, 2006, 12:38pm » |
Quote Modify
|
To each configuration of the deck, associate 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
2k-1 - (0+21+...+2k-2) = 2.
Hence there can be no more than 2n-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].
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Reversish Card Shuffling
« Reply #10 on: Nov 9th, 2006, 2:17pm » |
Quote Modify
|
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
|
| « Last Edit: Nov 9th, 2006, 2:19pm by Sameer » |
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print