Sources page biographical material

5.Z.6. MIXTURES
Ball. MRE, 5th ed., 1911. Loc. cit. in 5.Z. P. 122: "There are endless similar questions in which combinations of pieces are involved." 4 queens and king or queen or bishop or knight or rook or pawn can strongly dominate 8 x 8.

King. Best 100. 1927.

No. 77, pp. 30 & 57. 4 queens and a rook strongly dominate 8 x 8.

No. 78, pp. 30 & 57. 4 queens and a bishop strongly dominate 8 x 8.

5.AA. CARD SHUFFLING
New section. I have been meaning to add this sometime, but I have just come across an expository article, so I am now starting. The mathematics of this gets quite formidable. See 5.AD for a somewhat related topic.

A faro, weave, dovetail or perfect (riffle) shuffle starts by cutting the deck in half and then interleaving the two halves. When the deck has an even number of cards, there are two ways this can happen -- the original top card can remain on top (an out shuffle) or it can become the second card of the shuffled deck (an in shuffle). E.g. if our deck is 123456, then the out shuffle yields 142536 and the in shuffle yields 415263. Note that removing the first and last cards converts an out shuffle on 2n cards to an in shuffle on 2n-2 cards. When the deck has an odd number of cards, say 2n+1, we cut above or below the middle card and shuffle so the top of the larger pile is on top, i.e. the larger pile straddles the smaller. If the cut is below the middle card, we have piles of n+1 and n and the top card remains on top, while cutting above the middle card leaves the bottom card on bottom. Removing the top or bottom card leaves an in shuffle on 2n cards.

Monge's shuffle takes the first card and then alternates the next cards over and under the resulting pile, so 12345678 becomes 86421357.

At G4G2, 1996, Max Maven gave a talk on some magic tricks based on card shuffling and gave a short outline of the history. The following is an attempt to summarise his material. The faro shuffle, done by inserting part of the deck endwise into the other part, but not done perfectly, began to be used in the early 18C and a case of cheating using this is recorded in 1726. The riffle shuffle, which is the common American shuffle, depends on mass produced cards of good quality and began to be used in the mid 19C. However, magicians did not become aware of the possibilities of the perfect shuffle until the mid 20C, despite the early work of Stanyans C. O. Williams and Charles T. Jordan in the 1910s.

Hooper. Rational Recreations. Op. cit. in 4.A.1. 1774. Vol. 1, pp. 78-85: Of the combinations of the cards. This describes a shuffle, where one takes the top two cards, then puts the next two cards on top, then the next three cards underneath, then the next two on top, then the next three underneath. For ten cards 1234567890, it produces 8934125670, a permutation of order 7. Tables of the first few repetitions are given for 10, 24, 27 and 32 cards, having orders 7, 30, 30, 156.

The Secret Out. 1859. Permutation table, pp. 394-395 (UK: 128-129). Describes Hooper's shuffle for ten cards.

Bachet-Labosne. Problemes. 3rd ed., 1874. Supp. prob. XV, 1884: 214-222. Discusses Monge's shuffle and its period.

John Nevil Maskelyne. Sharps and Flats. 1894. ??NYS -- cited by Gardner in the Addendum of Carnival. "One of the earliest mentions". Called the "faro dealer's shuffle".

Ahrens. MUS I. 1910. Ein Kartenkunststück Monges, pp. 152-145. Expresses the general form of Monge's shuffle and finds its order for n = 1, 2, ..., 10. Mentions the general question of finding the order of a shuffle.

Charles T. Jordan. Thirty Card Mysteries. The author, Penngrove, California, 1919 (??NYS), 2nd ed., 1920 (?? I have copy of part of this). Cited by Gardner in the Addendum to Carnival. First magician to apply the shuffle, but it was not until late 1950s that magicians began to seriously use and study it. The part I have (pp. 7-10) just describes the idea, without showing how to perform it. The text clearly continues to some applications of the idea. This material was reprinted in The Bat (1948-1949).

Frederick Charles Boon. Shuffling a pack of cards and the theory of numbers. MG 15 (1930) 17-20. Considers the Out shuffle and sees that it relates to the order of 2 (mod 2n+1) and gives some number theoretic observations on this. Also considers odd decks.

J. V. Uspensky & M. A. Heaslet. Elementary Number Theory. McGraw-Hill, NY, 1939. Chap. VIII: Appendix: On card shuffling, pp. 244-248. Shows that an In shuffle of a deck of 2n cards takes the card in position i to position 2i (mod 2n+1), so the order of the permutation is the exponent or order of 2 (mod 2n+1), which is 52 when n = 26. [Though not discussed, this shows that the order of the Out shuffle is the order of 2 (mod 2n-1), which is only 8 for n = 26. And the order of a shuffle of 2n+1 cards is the order of 2 (mod 2n+1).] Monge's shuffle is more complex, but leads to congruences (mod 4n+1) and has order equal to the smallest exponent e such that 2^e  ±1 (mod 4n+1), which is 12 for n = 26.

T. H. R. Skyrme. A shuffling problem. Eureka 7 (Mar 1942) 17-18. Describes Monge's shuffle with the second card going under or over the first. Observes that in the under shuffle for an even number of cards, the last card remains fixed, while the over shuffle for an odd number of cards also leaves the last card fixed. By appropriate choice, one always has the n-th card becoming the first. Finds the order of the shuffle essentially as in Uspensky & Heaslet. Makes some further observations.

N. S. Mendelsohn, proposer and solver. Problem E792 -- Shuffling cards. AMM 54 (1947) 545 ??NYS & 55 (1948) 430-431. Shows the period of the out shuffle is at most 2n-2. Editorial notes cite Uspensky & Heaslet and MG 15 (1930) 17-20 ??NYS.

Charles T. Jordan. Trailing the dovetail shuffle to its lair. The Bat (Nov, Dec 1948; Jan, Feb, Mar, 1949). ??NYS -- cited by Gardner. I have No. 59 (Nov 1948) cover & 431-432, which reprints some of the material from his book.

Paul B. Johnson. Congruences and card shuffling. AMM 63 (1956) 718-719. ??NYS -- cited by Gardner.

Alexander Elmsley. Work in Progress. Ibidem 11 (Sep 1957) 222. He had previously coined the terms 'in' and 'out' and represented them by I and O. He discovers and shows that to put the top card into the k th position, one writes k-1 in binary and reads off the sequence of 1s and 0s, from the most significant bit, as I and O shuffles. He asks but does not solve the question of how to move the k-th card to the top -- see Bonfeld and Morris.

Alexander Elmsley. The mathematics of the weave shuffle, The Pentagram 11:9 (Jun 1957) 70 71; 11:10 (Jul 1957) 77-79; 11:11 (Aug 1957) 85; 12 (May 1958) 62. ??NYR -- cited by Gardner in the bibliography of Carnival, but he doesn't give the Ibidem reference in the bibliography, so there may be some confusion here?? Morris only cites Pentagram.

Solomon W. Golomb. Permutations by cutting and shuffling. SIAM Review 3 (1961) 293 297. ??NYS -- cited by Gardner. Shows that cuts and the two shuffles generate all permutations of an even deck. However, for an odd deck of n cards, the two kinds of shuffles can be intermixed and this only changes the cyclic order of the result. Since cutting also only changes the cyclic order, the number of possible permutations is n times the order of the shuffle.

Gardner. SA (Oct 1966) = Carnival, chap. 10. Defines the in and out shuffles as above and gives the relation to the order of 2. Notes that it is easier to do the inverse operations, which consist of extracting every other card. Describes Elmsley's method. Addendum says no easy method is known to determine shuffles to bring the k th card to the top.

Murray Bonfeld. A solution to Elmsley's problem. Genii 37 (May 1973) 195-196. Solves Elmsley's 1957 problem by use of an asymmetric in-shuffle where the top part of the deck has 25 cards, so the first top card becomes second and the last two cards remain in place. (If one ignores the bottom two cards this is an in-shuffle of a 50 card deck.)

S. Brent Morris. The basic mathematics of the faro shuffle. Pi Mu Epsilon Journal 6 (1975) 86-92. Obtains basic results, getting up to Elmsley's work. His reference to Gardner gives the wrong year.

Israel N. Herstein & Irving Kaplansky. Matters Mathematical. 1974; slightly revised 2nd ed., Chelsea, NY, 1978. Chap. 3, section 4: The interlacing shuffle, pp. 118-121. Studies the permutation of the in shuffle, getting same results as Uspensky & Heaslet.

S. Brent Morris. Faro shuffling and card placement. JRM 8:1 (1975) 1-7. Shows how to do the faro shuffle. Gives Elmsley's and Bonfeld's results.

Persi Diaconis, Ronald L. Graham & William M. Kantor. The mathematics of perfect shuffles. Adv. Appl. Math. 4 (1983) 175-196. ??NYS.

Steve Medvedoff & Kent Morrison. Groups of perfect shuffles. MM 60:1 (1987) 3-14. Several further references to check.

Walter Scott. Mathematics of card sharping. M500 125 (Dec 1991) 1-7. Sketches Elmsley's results. States a peculiar method for computing the order of 2 (mod 2n+1) based on adding translates of the binary expansion of 2n+1 until one obtains a binary number of all 1s. The number of ones is the order a and the method is thus producing the smallest a such that 2^a-1 is a multiple of 2n+1.

John H. Conway & Richard K. Guy. The Book of Numbers. Copernicus (Springer-Verlag), NY, 1996. Pp. 163-165 gives a brief discussion of perfect shuffles and Monge's shuffle.