HOME

TheInfoList



OR:

The faro shuffle (American), weave shuffle (British), or dovetail shuffle is a method of
shuffling 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. __TOC__ Techniques Over ...
playing card A playing card is a piece of specially prepared card stock, heavy paper, thin cardboard, plastic-coated paper, cotton-paper blend, or thin plastic that is marked with distinguishing motifs. Often the front (face) and back of each card has a f ...
s, 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. Mathematicians use the term "faro shuffle" to describe a precise rearrangement of a deck into two equal piles of 26 cards which are then interwoven perfectly.


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 zipper, zip, fly, or zip fastener, formerly known as a clasp locker, is a commonly used device for binding together two edges of fabric or other flexible material. Used in clothing (e.g. jackets and jeans), luggage and other bags, camping ...
. A flourish can be added by springing the packets together by applying pressure and bending them from above. 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". 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 Persi Warren Diaconis (; born January 31, 1945) is an American mathematician of Greek descent and former professional magician. He is the Mary V. Sunseri Professor of Statistics and Mathematics at Stanford University. He is particularly kno ...
.


Perfect shuffles

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 Alex Elmsley (2 March 1929 – 8 January 2006) was a Scottish magician and computer programmer. He was notable for his invention of the ''Ghost Count'' or '' Elmsley Count'', creating mathematical card tricks, and for publishing on the mathemat ...
. 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 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. In general, k perfect in-shuffles will restore the order of an n-card deck if 2^k\equiv 1\pmod. For example, 52 consecutive in-shuffles restore the order of a 52-card deck, because 2^\equiv 1\pmod. In general, k perfect out-shuffles will restore the order of an n-card deck if 2^k\equiv 1\pmod. 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. 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 In number theory, given a positive integer ''n'' and an integer ''a'' coprime to ''n'', the multiplicative order of ''a'' modulo ''n'' is the smallest positive integer ''k'' such that a^k\ \equiv\ 1 \pmod n. In other words, the multiplicative ord ...
of 2
modulo In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation). Given two positive numbers and , modulo (often abbreviated as ) is ...
(''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, ... . According to
Artin's conjecture on primitive roots In number theory, Artin's conjecture on primitive roots states that a given integer ''a'' that is neither a square number nor −1 is a primitive root modulo infinitely many primes ''p''. The conjecture also ascribes an asymptotic density to t ...
, it follows that there are infinitely many deck sizes which require the full set of ''n'' shuffles. The analogous operation to an out shuffle for an infinite sequence is the
interleave sequence In mathematics, an interleave sequence is obtained by merging two sequences via an in shuffle. Let S be a set, and let (x_i) and (y_i), i=0,1,2,\ldots, be two sequences in S. The interleave sequence is defined to be the sequence x_0, y_0, x_1 ...
.


Example

For simplicity, we will use a deck of six cards. The following shows the order of the deck after each in shuffle of an in-shuffle. Notice that a deck of this size returns to its original order after 3 in shuffles. :: The following shows the order of the deck after each out shuffle. Notice that a deck of this size returns to its original order after 4 out shuffles. ::


As deck manipulation

Magician
Alex Elmsley Alex Elmsley (2 March 1929 – 8 January 2006) was a Scottish magician and computer programmer. He was notable for his invention of the ''Ghost Count'' or '' Elmsley Count'', creating mathematical card tricks, and for publishing on the mathemat ...
discovered 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 A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" ( zero) and "1" (one). The base-2 numeral system is a positional notati ...
, 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 (10102). 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 10102 or 000010102; preliminary out-shuffles will not affect the outcome because out-shuffles always keep the top card on top.


Group theory aspects

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a perfect shuffle can be considered an element of the
symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group ...
. More generally, in S_, the perfect shuffle is the permutation that splits the set into 2 piles and interleaves them: :S_=\begin 1 & 2 & 3 & 4 & \cdots & 2n-1 & 2n\\ 1 & n+1 & 2 & n+2 & \cdots & n & 2n \end In other words, it is the map :k \mapsto \begin \frac & k \ \text\\ n+\frac & k \ \text \end Analogously, the (k,n)-perfect shuffle permutationEllis, Fan, and Shallit 2002 is the element of S_ 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(\rho_n) = (-1)^\mbox(\rho_). The sign is thus 4-periodic: :\mbox(\rho_n) = (-1)^ = \begin +1 & n \equiv 0,1 \pmod\\ -1 & n \equiv 2,3 \pmod \end The first few perfect shuffles are: \rho_0 and \rho_1 are trivial, and \rho_2 is the transposition (23) \in S_4.


Notes


References

* * * * * *{{cite arXiv , last = Jain , first = Peiyush , title = A simple in-place algorithm for in shuffles , date=May 2008 , class = cs.DS , eprint = 0805.1598 Card game terminology Card magic Card shuffling Permutation groups