# Faro shuffle

The faro shuffle (American), weave shuffle (British), or dovetail shuffle is a method of shuffling playing cards.

Mathematicians use the term "faro shuffle" for a shuffle in which the deck is split into equal halves of 26 cards that are then interwoven perfectly.[1]

Magicians use these terms for a particular technique (which Diaconis, Graham, and Kantor call "the technique")[2] for achieving this result.

## Description

A right-handed practitioner holds the cards from above in the right and from below in the left hand. The deck is separated into two preferably equal parts by simply lifting up half the cards with the right thumb slightly and pushing the left hand's packet forward away from the right hand. The two packets are often crossed and tapped against each other to align them. They are then pushed together on the short sides and bent either up or down. The cards will then alternately fall onto each other, ideally alternating one by one from each half, much like a zipper. A flourish can be added by springing the packets together by applying pressure and bending them from above.[3]

A game of Faro ends with the cards in two equal piles that the dealer must combine to deal them for the next game. According to the magician John Maskelyne, the above method was used, and he calls it the "faro dealer's shuffle".[4] Maskelyne was the first to give clear instructions, but the shuffle was used and associated with faro earlier, as discovered mostly by the mathematician and magician Persi Diaconis.[5]

A faro shuffle which leaves the original top card at the top and the original bottom card at the bottom is known as an out-shuffle, while one that moves the original top card to second and the original bottom card to second from the bottom is known as an in-shuffle. These names were coined by the magician and computer programmer Alex Elmsley.[6] A perfect faro shuffle, where the cards are perfectly alternated, requires the shuffler to cut the deck into two equal stacks and apply just the right pressure when pushing the half decks into each other.

The faro shuffle is a controlled shuffle that does not fully randomize a deck. If one manages to perform eight perfect faro out-shuffles in a row, then the deck of 52 cards will be restored to its original order. If one can do perfect in-shuffles, then 26 shuffles will reverse the order of the deck and 26 more will restore it to its original order.[7] If an additional 12 cards are added to the deck, so that the deck contains 64 cards, only 6 faro shuffles are required to maintain the order of a deck, compared to 8 shuffles for a 52-card deck.

## Group theory aspects

In mathematics, a perfect shuffle can be considered an element of the symmetric group.

More generally, in ${\displaystyle S_{2n}}$ , the perfect shuffle is the permutation that splits the set into 2 piles and interleaves them:

${\displaystyle S_{2n}}$ =${\displaystyle {\begin{pmatrix}1&2&3&4&\cdots \\1&n+1&2&n+2&\cdots \end{pmatrix}}}$

In other words, it is the map

${\displaystyle k\mapsto {\begin{cases}\left\lceil {\frac {k+1}{2}}\right\rceil &k\ {\text{odd}}\\n+{\frac {k}{2}}&k\ {\text{even}}\end{cases}}}$

Analogously, the ${\displaystyle (k,n)}$ -perfect shuffle permutation[8] is the element of ${\displaystyle S_{kn}}$  that splits the set into k piles and interleaves them.

The ${\displaystyle (2,n)}$ -perfect shuffle, denoted ${\displaystyle \rho _{n}}$ , is the composition of the ${\displaystyle (2,n-1)}$ -perfect shuffle with an ${\displaystyle n}$ -cycle, so the sign of ${\displaystyle \rho _{n}}$  is:

${\displaystyle {\mbox{sgn}}(\rho _{n})=(-1)^{n+1}{\mbox{sgn}}(\rho _{n-1}).}$

The sign is thus 4-periodic:

${\displaystyle {\mbox{sgn}}(\rho _{n})=(-1)^{\lfloor n/2\rfloor }={\begin{cases}+1&n\equiv 0,1{\pmod {4}}\\-1&n\equiv 2,3{\pmod {4}}\end{cases}}}$

The first few perfect shuffles are: ${\displaystyle \rho _{0}}$  and ${\displaystyle \rho _{1}}$  are trivial, and ${\displaystyle \rho _{2}}$  is the transposition ${\displaystyle (23)\in S_{4}}$ .

## Number theory aspects

### Out Shuffle

Below, we will be investigating how a perfect (faro) shuffle arranges the deck after each occurrence.

In order to do this, think of the cards being relabeled in numerical order with the first card being labeled 0 and the last card being labeled 51. Then, the deck is split and shuffled, making the order 0, 26, 1, 27, 2, 28, …. 25, 51.

This can be described as a function with the value being the card's new place in the deck.

f(0)= 0

f(1)= 2

f(2)= 4

f(3)= 6

f(25)= 50

This makes the function f(x)= 2x until the original place value passes 25.

f(26)= 1

f(27)= 3

f(28)= 5

f(29)= 7

f(51)= 51

Due to the repetitive nature of both halves of this problem, modular arithmetic is the best way for it to be modeled. The function describing the out shuffle would be:

f(x)= 2x (mod 51)

This models the first out shuffle.

Repetitive out shuffles with x being the location before any shuffles were made are:

2nd shuffle f(x)= 4x (mod 51)

3rd shuffle f(x)= 8x (mod 51)

Since each shuffle is applying the 2x (mod 51) function, and it is multiplicative, not additive, we can create one function with k being the number of shuffles:

f(x)= 2kx (mod 51)

In order to get back to the original deck order f(x)=x, the equation for resetting the deck order be:

1≡ 2k (mod 51)

The equation above would be solved using a multiplicative order, which is the lowest exponent k that is equal to 1 (mod 51).

This makes the minimum number of shuffles to return the deck to its original order, ord51 (2) which is equal to 8.

### In Shuffle

How an in shuffle mixes up a deck can best be analyzed using a similar set but this time the cards will be labeled 1 to 52.

The deck will start off being 1,2,3,4,5, … 52. After the first in-shuffle it will become 27, 1, 28, 2, 29, 3, … 52, 26.

This can be described as a function with the value being the card's new place in the deck.

g(1)= 2

g(2)= 4

g(3)= 6

g(26)= 52

Again, this looks like a simple function of g(x)= 2x, but it changes once the cards pass 26.

g(27)= 1

g(28) = 3

g(29) = 5

g(52)= 51

Modular arithmetic will be used again to model this function but with slightly different numbers. This equation is:

g(x)= 2x (mod 53)

For the same reasoning as before, the placement of cards as more shuffles occur goes as follows:

2nd shuffle 4x (mod 53)

3rd shuffle 8x (mod 53)

Thus, making the general equation for in shuffling being:

g(x) = 2kx (mod 53) for k shuffles

The number of shuffles required for the deck to reset is when g(x)=x making the equation be:

1≡ 2k (mod 53)

This makes the minimum number of shuffles to get the deck back to original deck order be ord53(2) which is equal to 52.

Both of these methods of shuffling cards will reset the deck eventually regardless of the size of the deck of cards. The same process is used to figure out how many in or out shuffles are necessary to return to the original order. The maximum number of shuffles will be the number of cards that are in the given deck.

### Discovery

An interesting discovery of how the positions of the cards are affected after different in shuffles and out shuffles was made by magician Alex Elmsley. He discovered that “to bring a card on top of the pack to any desired position, subtract one from the desired position, express the result as a binary number, and use it as instructions for a series of in- and out-shuffles, and the card will end where you want it.” For this process the 1's are in shuffles and the 0's are out shuffles.

For example, if the top card was wanted in the 23rd position first, the 23 would become 22. Then, in binary, 22 is 10110, so the series of shuffles would be in, out, in, in, out.

## Notes

1. ^ Morris 1998, 13
2. ^ Diaconis, Graham, and Kantor 1983, 188
3. ^ Morris 1998, 111
4. ^ Maskelyne 1894, 204
5. ^ Morris 1998, 8
6. ^ Morris 1998, 11–12
7. ^ Diaconis, Graham, and Kantor 1983, 193
8. ^ Ellis, Fan, and Shallit 2002

## References

• Diaconis, P.; Graham, R. L.; Kantor, W. M. (1983). "The mathematics of perfect shuffles" (PDF). Advances in Applied Mathematics. 4 (2): 175–196. doi:10.1016/0196-8858(83)90009-X.