The mathematics of card shuffling
A faro shuffle
is a technique for shuffling a deck of cards by cutting the deck exactly in half and riffling the two halves together so that they alternate perfectly. Performing a sequence of eight identical faro shuffles will return a standard deck of cards to its original order.
There are actually two types of faro shuffle, depending on the way in which the cards are interlaced in the last step. If the original top card stays on the outside
after riffling (i.e., it stays on the top), then the shuffle is called an out-shuffle
. On the other hand, if the top card moves one place down to the inside
after riffling, then the shuffle is called an in-shuffle
Some card magic tricks are based on a palindrome-like property of faro shuffles that is sometimes called stay stack
. This means that two cards that are symmetrically placed around the middle of the pack (for example, the third card from the top and the third card from the bottom) will stay symmetrically placed after a sequence of faro shuffles. This means that the order of the entire pack of cards after a sequence of faro shuffles can be determined from a knowledge of the top half of the pack together with a knowledge of the initial ordering.
Using a combination of out-shuffles and in-shuffles, a pack of cards can potentially be arranged in a large number of ways. Despite this, it is not possible to transform the deck into an arbitrary order using a combination of faro shuffles. Determining which arrangements can be reached using shuffles of various types is an interesting problem, which is investigated in the recent paper The mathematics of the flip and horseshoe shuffles
by Steve Butler
, Persi Diaconis
and Ron Graham
). As the title suggests, the authors are interested in shuffles other than the standard faro shuffles; the latter were studied in a 1983 paper by Diaconis, Graham, and William Kantor
The flip shuffle
is illustrated in the picture. It is the same as the faro shuffle except that one of the halves of the pack is turned upside down before being shuffled back in. As with the faro shuffle, the flip shuffle comes in “out” and “in” versions. The picture illustrates the “out” version, if we assume that all the cards were face up to begin with. Theorem 2 of the paper explains how if n is a positive integer, then the combinatorics of shuffling a deck of 2n cards with flip shuffles is essentially the same as that of shuffling a deck of 4n cards with the usual faro shuffles. For example, if we take n=13, shuffling a deck of 26 cards with flip shuffles is very similar to shuffling a standard deck of 52 cards with faro shuffles. “Very similar” means not only that the number of possible arrangements of cards is the same in each case, but also that the groups of symmetries that arise are essentially the same (“canonically isomorphic”).
The reason for this close similarity has to do with the “stay stack” property. An obvious way to index a deck of cards is by the numbers 1, 2, 3, ..., 52, where 1 refers to the top card, but it turns out to be useful instead to index the cards with the numbers 1, 2, 3, ..., 26, –26, –25, –24, ..., –1, where 1 is the top card and –1 is the bottom card. Now imagine shuffling the 52 cards using faro shuffles, then cutting the pack and selecting the top half. Within the 26 top cards, we can then replace each a card with a negative index (say, –11) with a flipped-over version of the corresponding positively indexed card (with index 11). Theorem 2 is proved by using this identification.
The part of the paper by Butler, Diaconis and Graham that deals with horseshoe shuffles is particularly interesting. A horseshoe shuffle
is the same as a flip shuffle, except that every card remains facing the correct way at every step of the shuffle. Like the other shuffles, a horseshoe shuffle comes in “out” and “in” varieties. Theorem 3 of the paper lists the possible groups of symmetries arising from horseshoe shuffles on a deck of 2n cards, where n is a positive integer. If n is odd (and not equal to 3) then the group is the full symmetric group on 2n objects; this means that in this case, the pack can be mixed in any way you like using a combination of horseshoe shuffles. If n is even (and not equal to 6 or to a power of 2) then the group is the alternating group on 2n objects; this means that it is possible to reach exactly half of the possible permutations of the deck using horseshoe shuffles.
The authors admit to being annoyed at not being able to identify the symmetry group in general in the case where n is a power of 2. However, if n=3, then the group turns out to be the symmetric group on 5 objects, and if n=6, something surprising happens: the symmetry group is the Mathieu group M_12
. The group M_12 is a famous example of a simple group
. Groups are mathematical objects that measure symmetry in the same way that numbers measure quantity, and simple groups play the role in group theory that prime numbers play in arithmetic. With 26 exceptions, all finite simple groups fit into 18 infinite families.
The group M_12, which consists of 95040 symmetries, is the second smallest of the 26 exceptional groups. This means that a deck of 12 cards can be horseshoe shuffled to exactly 95040 (8x9x10x11x12) different configurations. The group M_12 has the property of being sharply 5-transitive
, which means that it is possible to use horseshoe shuffles to shuffle your five favourite cards in a deck of 12 to your five favourite positions, in any order you like (“5-transitive”), but also that the position of the other seven cards is then completely fixed (“sharply”).Relevant links
The Mathieu groups: http://en.wikipedia.org/wiki/Mathieu_group
Faro shuffle: http://en.wikipedia.org/wiki/Faro_shuffle
The largest of the 26 sporadic finite simple groups is the Monster
, which is discussed in my post here: https://plus.google.com/101584889282878921052/posts/9sKMLRJYjna
The picture here appears in the paper by Butler, Diaconis and Graham, but I do not know who the photographer is.#mathematics #scienceeveryday #spnetwork