Math Puzzle: The longest shuffle


It will take a maximum of 30 shuffles before the deck returns to its original order.

Every shuffle, no matter how complicated, ultimately maps each position in the deck to another position, i.e., a shuffle is some permutation of the deck. Permutations can always be decomposed into discrete cycles. To understand this, consider the example shuffle given below, where the top card ends up in the sixth position, the second card moves to the top, etcetera.

Table lists the positions of ten cards before and after shuffling. The cards move positions as follows: one to six, two to one, three to eight, four to four, five to three, six to nine, seven to ten, eight to five, nine to two, ten to seven.

Follow the card that starts on top. The first shuffle moves it to position six, the second moves it from position six to position nine, the third to position two and the fourth back to position one. So it travels around a cycle of four positions: one → six → nine → two → one. Notice that the cards that begin in positions two, six and nine also travel along this same cycle before returning to their original positions. Following the other cards, you’ll find that this shuffle can be decomposed into cycles of lengths four, three, two and one. Every card belongs to some cycle, and no card belongs to two different cycles. (Every position points to one other position and is pointed to from one other position. To take part in two cycles, a position would have to point to two different places or be pointed to from two different places.)

Every shuffle can be decomposed in this way. The length of a cycle represents the number of cards in that cycle, so the lengths always sum to 10. For example, the shuffle that simply takes the top card and puts it on the bottom would create one big cycle of length 10. The vacuous “shuffle” that declines to move any cards decomposes into 10 “cycles” each of length one.

A card in a cycle of length three returns to its starting position after three shuffles and then again after six, nine, 12, and so on. So the whole deck is back in order the first time that every cycle has completed a whole number of trips around. That’s the least common multiple of the cycle lengths. To make the deck take as long as possible to return, we want to split 10 into cycle lengths with the largest possible least common multiple.

Cycles whose lengths share a common factor waste cards. Cycles of four and six, for example, are both back in place after 12 shuffles, but cycles of four and three are as well, and they leave you three additional cards to play with. So the best options use lengths with no common factors. The winner is 5 + 3 + 2 = 10, which takes 5 × 3 × 2 = 30 shuffles.

Fun fact: for a full deck of 52 cards, the longest shuffle uses cycles of length four, five, seven, nine, 11 and 13, plus three cards that stay in their original positions, and it takes 180,180 shuffles to restore the deck.



Source link

Donald Trump Steps Into ‘Rush Hour 4’ Plans as Jackie Chan and Chris Tucker Prepare to Return

Are crashing BAE Systems shares a dirt cheap buying opportunity?

Leave a Reply

Your email address will not be published. Required fields are marked *