Cards Reordering
A mind boggling brainteaser asked in this intern season's Jane Street Interview
The rudimentary method of shuffling a pack of cards is to take the pack face downwards in the left hand and then transfer them one by one to the right hand, putting the second on top of the first, the third under, the fourth above, and so on until all are transferred. If you do this with any even number of cards and keep on repeating the shuffle in the same way, the cards will in due time return to their original order. Try with 4 cards, you will find the order is restored in 3 shuffles. In face, where the number of cards is 2, 4, 8, 16, 32, 64, the number of shuffles to get them back to the original arrangement is 2, 3, 4, 5, 6, 7 respectively.
How many shuffles are necessary in the case of 14 cards?
Try to solve this problem yourself before moving on to the solution below
.
.
.
.
.
.
Solution
Each shuffle can be represented as a permutation in S_14, the symmetric group on 14 integers. This is because each of the cards is now permuted to some other spot in the deck, meaning that the shuffle operation can be represented as a permutation of 14 numbers. In two-row notation, this can be written as:
which, when expressed in cycle notation, would be:
This cycle is a disjoint one, as nothing maps back before the end. Thus, this permutation has order 14. This means 14 shuffles are required to get the cards back to their original arrangement.
.
.
😃 Over to you: Were you able to solve this?
👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.
👉 If you love reading this newsletter, feel free to share it with friends!
Really nice question
Loved it