Faro shuffle

This article's lead section may be too short to adequately summarize the key points. Please consider expanding the lead to provide an accessible overview of all important aspects of the article. (October 2018)

The faro shuffle (American), weave shuffle (British), or dovetail shuffle is a method of shuffling playing cards, in which half of the deck is held in each hand with the thumbs inward, then cards are released by the thumbs so that they fall to the table interleaved. Diaconis, Graham, and Kantor also call this the technique, when used in magic.^[1]

Mathematicians use the term "faro shuffle" to describe a precise rearrangement of a deck into two equal piles of 26 cards which are then interleaved perfectly.^[2]

A right-handed practitioner holds the cards from above in the left hand and from below in the right 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]

The faro shuffle is a controlled shuffle that does not fully randomize a deck.

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.

A faro shuffle that 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]

An out-shuffle has the same result as removing the top and bottom cards, doing an in-shuffle on the remaining cards, and then replacing the top and bottom cards in their original positions. Repeated out-shuffles cannot reverse the order of the entire deck, only the middle n−2 cards. Mathematical theorems regarding faro shuffles tend to refer to out-shuffles.

An in-shuffle has the same result as adding one extraneous card at the top and one extraneous card at the bottom, doing an out-shuffle on the enlarged deck, and then removing the extraneous cards. Repeated in-shuffles can reverse the order of the deck.

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]

In general, ${\displaystyle k}$ perfect in-shuffles will restore the order of an ${\displaystyle n}$-card deck if ${\displaystyle 2^{k}\equiv 1{\pmod {n+1}}}$. For example, 52 consecutive in-shuffles restore the order of a 52-card deck, because ${\displaystyle 2^{52}\equiv 1{\pmod {53}}}$.

In general, ${\displaystyle k}$ perfect out-shuffles will restore the order of an ${\displaystyle n}$-card deck if ${\displaystyle 2^{k}\equiv 1{\pmod {n-1}}}$. For example, if one manages to perform eight out-shuffles in a row, then the deck of 52 cards will be restored to its original order, because ${\displaystyle 2^{8}\equiv 1{\pmod {51}}}$. However, only 6 faro out-shuffles are required to restore the order of a 64-card deck.

In other words, the number of in-shuffles required to return a deck of cards of even size n, to original order is given by the multiplicative order of 2 modulo (n + 1).

For example, for a deck size of n=2, 4, 6, 8, 10, 12 ..., the number of in-shuffles needed are: 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, ... (sequence A002326 in the OEIS).

According to Artin's conjecture on primitive roots, it follows that there are infinitely many deck sizes which require the full set of n shuffles.^[8]

The analogous operation to an out-shuffle for an infinite sequence is the interleave sequence.

For simplicity, we will use a deck of six cards.

The following shows the order of the deck after each in-shuffle. A deck of this size returns to its original order after 3 in-shuffles.

Step	Top Card	2	3	4	5	Bottom Card
Start
1
2
3

The following shows the order of the deck after each out-shuffle. A deck of this size returns to its original order after 4 out-shuffles.

Step	Top Card	2	3	4	5	Bottom Card
Start
1
2
3
4

Magician Alex Elmsley discovered^{[citation needed]} that a controlled series of in- and out-shuffles can be used to move the top card of the deck down into any desired position. The trick is to express the card's desired position as a binary number, and then do an in-shuffle for each 1 and an out-shuffle for each 0.

For example, to move the top card down so that there are ten cards above it, express the number ten in binary (1010₂). Shuffle in, out, in, out. Deal ten cards off the top of the deck; the eleventh will be your original card. Notice that it doesn't matter whether you express the number ten as 1010₂ or 00001010₂; preliminary out-shuffles will not affect the outcome because out-shuffles always keep the top card on top.

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 &2n-1&2n\\1&n+1&2&n+2&\cdots &n&2n\end{pmatrix}}}$

In other words, it is the map

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

Analogously, the ${\displaystyle (k,n)}$-perfect shuffle permutation^[9] 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}}$.

• Diaconis, Persi; 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.

• Ellis, J.; Fan, H.; Shallit, J. (2002). "The Cycles of the Multiway Perfect Shuffle Permutation" (PDF). Discrete Mathematics & Theoretical Computer Science. 5: 169–180. doi:10.46298/dmtcs.308. Retrieved 26 Dec 2013.

• Maskelyne, John (1894). Sharps and Flats: A Complete Revelation of the Secrets of Cheating at Games of Chance and Skill. Longmans, Green and Company. Retrieved 26 Dec 2013.

• Morris, S. Brent (1998). Magic Tricks, Card Shuffling, and Dynamic Computer Memories. The Mathematical Association of America. ISBN 0-883-85527-5. Retrieved 26 Dec 2013.

• Kolata, Gina (April 1982). "Perfect Shuffles and Their Relation to Math". Science. 216 (4545): 505–506. Bibcode:1982Sci...216..505K. doi:10.1126/science.216.4545.505. PMID 17735734.

• Jain, Peiyush (May 2008). "A simple in-place algorithm for in-shuffles". arXiv:0805.1598 [cs.DS].