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

 Faulty Card Shuffler (Posted on 2013-07-24)
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.)
 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

 Search: Search body:
Forums (0)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: