Faro shuffle

Last updated April 29, 2024

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]

Description

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]

Perfect shuffles

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, $k$ perfect in-shuffles will restore the order of an $n$ -card deck if $2^{k}\equiv 1{\pmod {n+1}}$ . For example, 52 consecutive in-shuffles restore the order of a 52-card deck, because $2^{52}\equiv 1{\pmod {53}}$ .

In general, $k$ perfect out-shuffles will restore the order of an $n$ -card deck if $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 $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.

Example

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

As deck manipulation

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.

Group theory aspects

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

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

S_{2n}

=

{\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

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

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

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

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

The sign is thus 4-periodic:

{\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: $\rho _{0}$ and $\rho _{1}$ are trivial, and $\rho _{2}$ is the transposition $(23)\in S_{4}$ .

Notes

↑ Diaconis, Graham, and Kantor 1983, 188
↑ Morris 1998, 13
↑ Morris 1998, 111
↑ Maskelyne 1894, 204
↑ Morris 1998, 8
↑ Morris 1998, 11–12
↑ Diaconis, Graham, and Kantor 1983, 193
↑ Real v recreational mathematics, Peter Cameron, April 10, 2014.
↑ Ellis, Fan, and Shallit 2002

Related Research Articles

In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo of an odd prime number p: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is −1. Its value at zero is 0.

Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to help ensure that the shuffler has not manipulated the outcome.

The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1. It concerns sequences of integers in which each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence. The conjecture has been shown to hold for all positive integers up to 2.95×10²⁰, but no general proof has been found.

In number theory, Euler's theorem states that, if $n$ and $a$ are coprime positive integers, then $is congruent to modulo n, where denotes Euler's totient function; that is$

In modular arithmetic, a number $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$ . That is, $g$ is a primitive root modulo $n$ if for every integer $a$ coprime to $n$ , there is some integer $k$ for which $g$ ^$k$ ≡ $a$ . Such a value $k$ is called the index or discrete logarithm of $a$ to the base $g$ modulo $n$ . So $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$ .

In theoretical computer science and cryptography, a trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction without special information, called the "trapdoor". Trapdoor functions are a special case of one-way functions and are widely used in public-key cryptography.

In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1878 and subsequently proved by Derrick Henry Lehmer in 1930.

In computational number theory, the Lucas test is a primality test for a natural number n; it requires that the prime factors of n − 1 be already known. It is the basis of the Pratt certificate that gives a concise verification that n is prime.

<span class="mw-page-title-main">Cube (algebra)</span> Number raised to the third power

In arithmetic and algebra, the cube of a number $n$ is its third power, that is, the result of multiplying three instances of $n$ together. The cube of a number or any other mathematical expression is denoted by a superscript 3, for example 2³ = 8 or $(x + 1) 3$ .

Pollard's rho algorithm is an algorithm for integer factorization. It was invented by John Pollard in 1975. It uses only a small amount of space, and its expected running time is proportional to the square root of the smallest prime factor of the composite number being factorized.

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.

In number theory, the von Staudt–Clausen theorem is a result determining the fractional part of Bernoulli numbers, found independently by Karl von Staudt and Thomas Clausen.

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:

In mathematics, the Zernike polynomials are a sequence of polynomials that are orthogonal on the unit disk. Named after optical physicist Frits Zernike, laureate of the 1953 Nobel Prize in Physics and the inventor of phase-contrast microscopy, they play important roles in various optics branches such as beam optics and imaging.

In mathematics, the Eisenstein integers, occasionally also known as Eulerian integers, are the complex numbers of the form

CEILIDH is a public key cryptosystem based on the discrete logarithm problem in algebraic torus. This idea was first introduced by Alice Silverberg and Karl Rubin in 2003; Silverberg named CEILIDH after her cat. The main advantage of the system is the reduced size of the keys for the same security over basic schemes.

In number theory, the Fermat quotient of an integer a with respect to an odd prime p is defined as

A Gilbreath shuffle is a way to shuffle a deck of cards, named after mathematician Norman Gilbreath. Gilbreath's principle describes the properties of a deck that are preserved by this type of shuffle, and a Gilbreath permutation is a permutation that can be formed by a Gilbreath shuffle.

In the mathematics of permutations and the study of shuffling playing cards, a riffle shuffle permutation is one of the permutations of a set of $items that can be obtained by a single riffle shuffle, in which a sorted deck of cards is cut into two packets and then the two packets are interleaved. Beginning with an ordered set, mathematically a riffle shuffle is defined as a permutation on this set containing 1 or 2 rising sequences. The permutations with 1 rising sequence are the identity permutations.$

In the mathematics of shuffling playing cards, the Gilbert–Shannon–Reeds model is a probability distribution on riffle shuffle permutations that has been reported to be a good match for experimentally observed outcomes of human shuffling, and that forms the basis for a recommendation that a deck of cards should be riffled seven times in order to thoroughly randomize it. It is named after the work of Edgar Gilbert, Claude Shannon, and J. Reeds, reported in a 1955 technical report by Gilbert and in a 1981 unpublished manuscript of Reeds.

References

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].

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Diaconis, Graham, and Kantor 1983, 188

[2] Morris 1998, 13

[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] Real v recreational mathematics, Peter Cameron, April 10, 2014.

[9] Ellis, Fan, and Shallit 2002

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]