The perfect shuffle
Tonight's idea
Cut a deck of 52 cards in half, 26 and 26, and interleave the halves perfectly: one card from each in turn. If the top card stays on top, this is an out-shuffle. Card magicians practise it for years. Do it eight times and every card is back where it started.
To see why, number the positions 0 to 51 from the top and follow one card. The top half, positions 0 to 25, lands on the even positions 0, 2, 4, …, 50: the card at position \(p\) goes to \(2p\). The bottom half, positions 26 to 51, fills the odd positions: 26 goes to 1, 27 goes to 3, so \(p\) goes to \(2p - 51\).
After one out-shuffle, the card at position \(p\) moves to \(2p \bmod 51\): the remainder when \(2p\) is divided by 51. The bottom card, position 51, stays put.
"Mod" is clock arithmetic on a clock with 51 hours (grade 6). Each shuffle doubles the position, so after \(k\) shuffles the card sits at \(2^k p \bmod 51\). Every card is home when \(2^k\) leaves remainder 1 on division by 51. And \(2^8 = 256 = 5 \times 51 + 1\). Eight shuffles.
Watch one: the card at position 10
Double, and subtract 51 whenever the answer reaches 51:
\[10 \to 20 \to 40 \to 80 - 51 = 29 \to 58 - 51 = 7 \to 14 \to 28 \to 56 - 51 = 5 \to 10.\]
Eight arrows, and the card is back at 10. It visited eight different positions on the way, and so does almost every card: the trip takes exactly eight steps because 8 is the first power for which \(2^k\) has remainder 1. A smaller deck makes the pattern easy to test by hand. With 8 cards the rule is \(2p \bmod 7\), and \(1 \to 2 \to 4 \to 8 - 7 = 1\): three shuffles, because \(2^3 = 7 + 1\). Try it with eight playing cards.
Your turn
- Follow the card at position 3 through eight out-shuffles of a 52-card deck, writing each position. Check that it comes home.
- A deck of 10 cards is out-shuffled; the rule is \(p \to 2p \bmod 9\). How many shuffles bring it back? Explain the answer using a power of 2.
- Which positions in the 52-card deck are already home after a single out-shuffle? Which are home after two? (Solve \(2p \equiv p\) and \(4p \equiv p\) modulo 51; remember \(51 = 3 \times 17\).)
- (a) List \(2^k \bmod 51\) for \(k = 1, 2, \dots, 7\). Why does this prove that no number of out-shuffles below eight restores the deck? (b) A friend says that after four shuffles the deck is "half way back", so many cards must be home. Which cards actually are? Use \(16p \equiv p\).
Stretch: the in-shuffle
If the top card goes second, it is an in-shuffle. Check that its rule is \(p \to (2p + 1) \bmod 53\) by testing \(p = 0\) and \(p = 26\). Follow the top card for five in-shuffles. If the deck comes home after \(k\) in-shuffles, which number must divide \(2^k - 1\)? Show that \(k = 8\) fails. (It takes 52.)
Answers
- \(3 \to 6 \to 12 \to 24 \to 48 \to 96 - 51 = 45 \to 90 - 51 = 39 \to 78 - 51 = 27 \to 54 - 51 = 3\). Home after eight.
- Six. \(2^1, \dots, 2^6\) leave remainders 2, 4, 8, 7, 5, 1 on division by 9, and the first remainder 1 is at \(2^6 = 64 = 7 \times 9 + 1\). (Check with a card: \(1 \to 2 \to 4 \to 8 \to 7 \to 5 \to 1\).)
- After one: \(2p \equiv p\) means \(p \equiv 0\), so only position 0, plus the bottom card 51 which never moves. After two: \(4p \equiv p\) means \(3p\) is a multiple of 51, so \(p\) is a multiple of 17: positions 0, 17 and 34 (and 51). Cards 17 and 34 simply swap places each shuffle.
- (a) \(2, 4, 8, 16, 32, 13, 26\). None is 1, so after \(k \lt 8\) shuffles the card at position 1 is at \(2^k \ne 1\): the deck is not restored. (b) \(16p \equiv p\) means \(15p\) is a multiple of 51, so \(5p\) is a multiple of 17, so \(p\) is: again only 0, 17, 34 and 51. Nobody else is home. There is no "half way".
Stretch. \(p = 0\) goes to 1 (the top card goes second) and \(p = 26\) goes to \(53 \bmod 53 = 0\) (the first card of the bottom half lands on top), as an in-shuffle should. Top card: \(1 \to 3 \to 7 \to 15 \to 31\). After \(k\) in-shuffles the top card is at \(2^k - 1 \bmod 53\), so coming home needs 53 to divide \(2^k - 1\). \(2^8 - 1 = 255 = 3 \times 5 \times 17\), not a multiple of 53. The first \(k\) that works is 52.