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).
(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.
Cycle length is not obvious
