All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Faulty Card Shuffler (Posted on 2013-07-24) Difficulty: 3 of 5
This card shuffler, instead of randomizing the positions of cards in the deck, always rearranges any given set of cards into the same new order.

If for example one puts all the hearts into the shuffler, in the order A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, and runs that through the shuffler first once, and then, without rearranging the cards, runs it through again, the resulting sequence after the second shuffle is always:

10, 9, Q, 8, K, 3, 4, A, 5, J, 6, 2, 7

The question is:

What was the order of the cards after the first run through this non-randomizing shuffler?


From the Skeptics' Guide to the Universe podcast episode of June 22, 2013 (episode 414).

See The Solution Submitted by Charlie    
Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts Cycle length is not obvious | Comment 4 of 10 |
(In reply to Solution by Brian Smith)

Sorry, but Brian's approach is not guaranteed to work.  There is no guarantee that the cards will be back in their starting positions after 13 shuffles.  It only works if repeated shuffles eventually cause every card to  be in every position before they are restored to their original position.


Here is an example of one that doesn't work that way:

Applying a single shuffle to
   A 2 3 4 5 6 7 8 9 10 J Q K  (0 shuffles)
Results in 
   2 3 4 A 6 7 8 9 10 J Q K 5 (1 shuffle)
After two shuffles it is at 
   3 4 A 2 7 8 9 10 J Q K 5 6 (2 shuffles)
Applying the two shuffle approach 6 more times results in
   3 4 A 2 9 10 J Q K 5 6 7 8 9 (14 shuffles)
And the 14th shuffle is definitely different from the 1st shuffle.

This is because subsequent shuffles cause the first 4 cards to repeat in a subcycle with a cycle length of 4, and the last 9 cards to repeat in a subcycle with a cycle length of 9. It takes 36 shuffles until the cards are in their initial position!

In general, if none of the cards are in their original positions after 2 shuffles, then shuffle does not have any sub-cycles of length 1 or 2.  It could, however, have any of the following:
3 + 3 + 3 + 4 (repeats every 12 shuffles)
3 + 3 + 7       (repeats after 21)
3 + 4 + 6       (repeats after 12)
3 + 5 + 5       (repeats after 15)
3 + 10           (repeats after 30)
4 + 4 + 5       (repeats after 20)
4 + 9             (repeats after 36)
5 + 8             (repeats after 40)
6 + 7             (repeats after 42)
13                 (repeats after 13)

Brian's approach only works in the last case, but without analysis we cannot tell if we are in fact dealing with the last case.  I think I will analyze the rest of the cases to see whether there is only one solution to this problem.




  Posted by Steve Herman on 2013-07-25 00:38:57
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information