Magical Mathematics: Recurring Cycles of Ideas of Cycles

In the December 2008 Card Colm What's Black and Red and Red All Over?, we borrowed from a chapter by Persi Diaconis & Ron Graham in the Martin Gardner tribute A Lifetime of Puzzles (AK Peters), presenting a simplified version of a terrific card trick which the first book author has been performing in public lectures for many years.

The basic binary de Bruijn sequence material from that book chapter was, in turn, a preview of Chapter Two ("In Cycles") of the new, long-awaited, book Magical Mathematics: The Mathematical Ideas that Animate Great Magic Tricks (Princeton University Press), a truly stunning exposition by two masters in the field.

With the kind permission of the authors, we wrap up 2011 with a stroll through further "de Bruijn sequence" styled card magic, this time from Chapter Four ("Universal Cycles") of the new volume.

Invariably Factor

The card tricks considered in the December 2008 Card Colm concerned circular arrangements of 2^k Black and Red cards (or 0s and 1s), half of each, with the property that sliding windows of k adjacent cards (or bits), obtained by starting anywhere in the circle and proceeding around it in one fixed direction, cycle through all possible arrangements of Black and Red (or 0s and 1s), in some order, each of the  2^k of these occurring exactly once. For example, the circle obtained by joining the ends of 0, 0, 0, 1, 1, 1, 0, 1 has the desired property for sliding windows of length 3.

The basic application is to a packet of say, 16 Black and 16 Red cards, suitably arranged, memorised, and then cut (namely, cycled) arbitrarily often. If five adjacent cards are selected from the resulting circle of 32 cards, it's possible to correctly identify all of them merely by finding out which ones are Red. Powers of 2 play a major role here; note that 32 =  2⁵ . Such de Bruijn sequences exist for any power of 2, and we also know how many there are. However, extending a trick like that just mentioned to a regular deck of 52 cards, necessarily being told which of six adjacent cards are Red, is a challenge, due to the desire to have the two ends of the deck connect up while preserving the moving window property.

In mathemagic, as in mathematics itself, there is a delightful give and take between powers of 2 (counting binary arrangements allowing repetition) and factorials (counting permutations, i.e., arrangements of numerous things without repeats). While it generally holds that  2^k < k!, this isn't true for some small k. Indeed, in the February 2005 Card Colm Fitch Four Glory, we exploited the fact that  2³ > 3!  to "extend" the classic two person Fitch Cheney five card trick from five to four cards. The original trick from the late 1940s took advantage of permutations, applied to the relative ranks within the deck of three of four displayed cards; the four card version from 1999 uses 3-bit arrangements, based on the face-up or face-down state of three displayed cards.

Rival Satellite

There are occasions in decision making when one has to be very careful with comparisons: witness non-transitive dice or Condorcet paradoxes. Sometimes one makes judgement calls based on very local information, as in the situations now explored.

Let's focus on the relative ranks of three adjacent values in a row or circle of numbers. There are six possibilities, namely the rank permutations LMH (representing Low, Medium, High), LMH, MLH, MHL, HLM, and HML. For instance, the circle obtained from 1, 2, 3, 4, 5, 6 (considered wrapped around to 1 again) produced LMH four times, then MHL and finally HLM.

There are 5!/2 = 60 different (reversible and spinnable) circles using these six numbers. Of these, consider the one obtained by connecting the ends of 1, 4, 6, 2, 5, 3:

	3						1
5								4
	2						6

This is highly desirable as it has real magic potential:








Each possible rank permutation of three objects occurs exactly once

considering the adjacent values: {1, 4, 6}, {4, 6, 2}, ..., {3, 1, 4}

for the circle obtained by joining the ends of 1, 4, 6, 2, 5, 3.

It follows that if three adjacent values of these six are chosen by different people, then one need only ask who has the largest and who has the smallest to be able to tell exactly which value each person has!

Interested readers may wish to investigate if, upon reflection (or rotation), the indicated circle is unique. Incidentally, to remember that circle, we found it helpful to think of the area of a circle of radius 25 (can you see why?).

Diaconis & Graham note that they found circles of length 4! = 24 and 5! = 120 for which sliding windows of length 4 and 5, respectively, cycle through all possible rank permutations of that many objects. They then conjectured, and eventually proved with the assistance of Fan Chung, that this could be done for any k in a suitable circle of length k!, although they report that their proof was difficult and non-constructive.

The cards in ordinary decks are not naturally numbered up to 24 or 120 however, instead consisting of four suits of thirteen repeated values. Now imagine a deck with five suits, from which we assemble a packet of all five Aces, 2s, 3s and 4s, but only four 5s, having 24 cards total. Ignoring suits, one can also pull this off with cards from two ordinary decks. Then the circle obtained by connecting the ends of







1, 2, 3, 4, 1, 2, 5, 3, 4, 1, 5, 3, 2, 1, 4, 5, 3, 2, 4, 1, 3, 2, 5, 4,
has the following property:







Each possible rank permutation of four objects occurs exactly once

considering the adjacent values: {1, 2, 3, 4}, {2, 3, 4, 1}, ..., {4, 1, 2, 3}.
(Notice that no ties are encountered above; however that possibility is also considered by Diaconis & Graham, a few pages later.)

It follows that if four adjacent cards of these 24 are chosen by different people, then one need only ask who has the largest, who has the second largest and who has the third largest, to be able to tell exactly which value each person has!

There is a reason Diaconis & Graham needed five copies of each card value above: a recent result of Robert Johnson establishes an earlier conjecture that k + 1 is the smallest number of distinct values that can be assembled into a circular deck of k! cards so that the relative order of each group of k adjacent cards is distinct.

Warmed Linens

There is much more fascinating material, both mathematical and magical, in the chapter "Universal Cycles" of the Magical Mathematics: The Mathematical Ideas that Animate Great Magic Tricks; in truth we've only skimmed the surface. There are many other wonderful chapters in that book too.

We'd be remiss if we didn't mention the Chapter Four opener, one of the superb co-creations with prolific magic inventor Ronald Wohl, which is presented there as motivation for the rank permutation explorations above. It uses the values in an ordinary deck. Here it is, stripped of all magic coating:








From a pre-arranged and cut deck of 52 cards, five adjacent ones are selected by five people.

One is able to identify all five cards based only on the knowledge of who holds the top three in rank.

For instance, after much cutting, and some blather about how "well-mixed" the cards are, have five consecutive ones selected by as many people. Say something like, "Those are your scores, ladies and gentlemen. The highest one gets Gold, the next highest Silver, the third highest Bronze. I'm afraid that's it, the other ones don't get anything." Then hand out mock medals. As soon as you know who gets which one, and assuming you have somehow internalised or memorised the initial deck set-up, you can then name the exact card (not just the value) which each of the five people has.

Why is there hope of pulling off such an effect? Basically because given any five adjacent cards, the number of Gold/Silver/Bronze arrangements of some three of them is 5x4x3 = 60, which is greater than 52, the number of cards (or possible positions) in a deck.

How does one actually come up with such an arrangement in the first place? Very carefully. Good luck! Feel free to post solutions below, along with tips for remembering the resulting decks.

Critical Chum Runs

It's interesting to note that Diaconis & Graham's 1, 4, 6, 2, 5, 3 also yields a sum-rich circulant for triples in the sense of June 2008's Card Colm.

	3						1
5								4
	2						6

What we mean here is that the six possible sums of three adjacent values are distinct. In fact, we get sums 8, 9, 10, 13, 12, 11, as we go around the circle, based on the central element of each sum, so that 8 = 4 + 1 + 3 is listed first, followed by 9 = 1 + 3 + 5, etc. Notice that these sums are the six consecutive numbers 8, 9, 10, 11, 12, 13 in a very easy to remember order. Hence, given the sum, it's not hard to backtrack and deduce the identity of the three cards which gave rise to it.

Prominent Ace Proofs

We suggest loading the top of a deck with six cards of the desired values, in any mixed suits you can remember, and maintaining them there throughout several fair-seeming shuffles. Alternatively, one could use the same six cards from two decks and maintain a top stack twice as large, one sequence of six card following the other. In any case, deal out six (or twelve) cards into a face-down circle and invite somebody to pick one card. A second person picks one of the cards beside it, and finally a third picks either of the two "exposed" cards in the broken circle. Have them compare cards and either report who has the highest and who has the lowest (or the Gold and the Silver), or announce the total of all three values.

For that matter, you can throw in the option of being told "the mode, median or mean"! (Of course, the first case cannot occur, but only you know that.) As long as nobody says "Two" or "Four," all is well; you should be able to say who had which card. If "two" or "four" is called out, you need to fish to determine if it's a median or mean, before successfully concluding the trick.

For the record, the circle of six numbers considered above is also product-rich for triples, so you could also request just the product. Only 12 turns up as both a sum and a product.

"Invariably factor" is an anagram of "binary v. factorial," "rival satellite" is an anagram of "it's all relative," "warmed linens" is an anagram of "medal winners," "critical chum runs" is an anagram of "sum-rich circulant," and "prominent ace proofs" is an anagram of "performance options." We feel compelled to mention that "laden priors" is an anagram of "Persi Ronald" and "magicians hoard" is an anagram of "Diaconis Graham."

A Third Selection of Mathemagical Amusements with Cards in Martin Gardner's Own Words

Around this time of the year—his birthday was 21st October—people gather at various locations around the world for a Celebration of Mind, to enjoy the legacy and interests of renowned man of letters and numbers Martin Gardner (1914-2010). There is still time to attend or host one this year!

For a quarter of a century, from 1956 to 1983, Gardner wrote an extremely popular and influential monthly column called "Mathematical Games" for Scientific American. Last year here, we marked the passing of this intellectual giant and prolific writer with two selections of mathematical card tricks and entertainments—in his own words—from books 1-4 and 7 & 10 of the resulting 15 collections. This time, we sample further expositions on the topic from books 5, 11 & 12 of the series.
Incidentally, these books can be enjoyed in full, text searchable form on a CD-ROM available from the MAA called Martin Gardner's Mathematical Games. Some of Martin's more famous columns from those years are accessible now at MAA Online. Personal reminiscences of the man (and more) can be found here.
The crystal clear words in italics below are all Martin's, but the section headings are our own.

Facing Up

Chapter 14 of The 6th Book of Mathematical Diversions from Scientific American (1971) is called "Mathematical Magic Tricks." After describing a trick with pennies devised by Jack Yates, Martin writes:
The following, contributed by the British magician Norman MacCleod to a magic magazine in the United States, The New Phoenix (No. 328, August, 1955), is one of the best. While someone deals the deck into four bridge hands the performer writes on a slip of paper: "There will be 22 face-up cards." This prediction is folded and placed aside. The spectator takes two of the piles, the magician takes the other two.
"I have selected a number from one to ten," says the performer. "I shall turn that number of cards face up in each of my piles." He proceeds to turn some cards face up but without letting anyone see how many.
The spectator is asked to do the same with his two piles: choose a number from one to tell and reverse that number of cards in each pile. The four piles are assembled, the deck spread and the face-up cards counted. There are 22. The prediction is unfolded and found to be correct.
To perform this trick you must cheat a bit. Any even number between 13 and 30 can be written in your prediction. This number, minus 13, tells you the total number of cards to leave face down in your two packets. In this case 22 minus 13 is 9, so you reverse, say, all but 5 cards in one pile and all but 4 in the other. Put your two piles together and one of the spectator's piles on top. Hold this large packet in your left hand and ask the spectator to cut his remaining pile into two parts. While attention is focused on the cutting casually turn over your left hand, thus secretly reversing all its cards. This large pile is sandwiched between the two halves of the cut pile.
All the cards are now together again and presumably no one knows how many of them are face up. Do you see why there must be 22? The procedure reverses 13 cards in the spectator's two piles for the same reason that Yates's coin trick works. The 9 cards you left face down are now face up, making 22 in all. The trick can be repeated using other even numbers in the prediction. Odd numbers should be avoided because the procedure, if it is done legitimately, could not produce an odd number of face-up cards.

Hard to Miss

In his book Knotted Doughnuts and Other Mathematical Entertainments (1986), following a discussion of the Birthday Paradox and variations, Martin writes:
Another simple demonstration of an event that seems improbable but actually is not can be given with a deck of playing cards. Shuffle the cards, then deal them while you recite their names in a predetermined order, say ace to king of spades followed by the same sequence for hearts, clubs and diamonds. The probability that a card named in advance, such as the queen of hearts, will be dealt when it is named is 1/52, but the probability that at least one card will be dealt when named is almost 2/3. If you name only the values, the probability of a "hit" rises to 98 percent, or very close to certain.
(Another Martin Gardner inspired 98% likely "hit"—which is also related to the Birthday Paradox—can be found in Better Poker Hands Guaranteed, the June 2006 Card Colm.)

Non-Transitive Authority

In his book Time Travel and Other Mathematical Bewilderments (1988), Martin has a terrific chapter on non-transitive paradoxes. In this exposition of an amazing and counter-intuitive phenomenon, he included this card implementation:
Many paradoxes of this type were jointly investigated by Leo Moser and J. W. Moon. Some of the Moser-Moon paradoxes underlie striking and little- known sucker bets. For example, let each row (or each column) of an order-3 magic-square matrix be a set of playing cards, say the ace, 6, and 8 of hearts for set A, the 3, 5, and 7 of spades for set B, and the 2, 4, and 9 of clubs for C. Each set is randomized and placed face down on a table. The sucker is allowed to draw a card from any set, then you draw a card from a different set.

The high card wins. It is easy to prove that no matter what set the sucker draws from, you can pick a set that gives you winning odds of five to four. Set A beats B, B beats C, and C beats A. The victim may even be allowed to decide each time whether the high or the low card wins. If you play low card wins, simply pick the winning pile with respect to a nontransitive circle that goes the other way. A good way to play the game is to use sets of cards from three decks with backs of different colors. The packet of nine cards is shuffled each time, then separated by the backs into three sets.

Be There and Be Square

The "Combinatorial Card Problems" chapter from the same book contains a wealth of material to be explored with a deck of cards. As Martin observes,
There is no end to the making of mathematical tricks, puzzles, and other recreations that employ playing cards. In this chapter we look at some new card problems and games, with emphasis on how they lead into significant areas of combinatorial theory.
Consider the following combinatorial way of dramatizing an important number theorem. Remove all the cards of one suit (say, spades) from a deck and arrange them in serial order from ace to king. (The jack, queen, and king, respectively, represent 11, 12, and 13.) Place them face down in a row with the ace at the left. The following turning procedure is now applied, starting at the left at each step and proceeding to the right:

1. Turn over every card.


2. Turn over every second card. (Cards 2, 4, 6, 8, 10, and Q are turned face down.)


3. Turn over every third card.


4. Continue in this manner, turning every fourth card, every fifth card, and so on until you turn over only the last card.

The high card wins. It is easy to prove that no matter what set the sucker draws Inspect the row. Note that all the cards except the ace, the 4, and the 9 are face down. These values happen to be square numbers. Is this an accident? Or is it an authentic hint of a general rule? A good classroom exercise is to prepare 100 small cards bearing numbers 1 through 100, stand them with their backs out in serial order on a blackboard ledge and apply the turning procedure. Sure enough, at the finish the only visible numbers will be the squares: 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. That is too large a sampling to be coincidental. The next step is to prove that no matter how large the deck, only squares survive the turning procedure.

A simple proof introduces one of the oldest and most fundamental of number theorems: A positive integer has an odd number of divisors (the divisors include 1 and the number itself), if and only if the number is a square. This is easy to see. Most divisors of a number come in pairs. Consider 72. The smallest divisor, 1, goes into the number 72 times, giving the pair 1 and 72. The next-larger divisor, 2, goes into the number 36 times, giving the pair 2 and 36. Similarly, 72 = 3 x 24 = 4 x 18 = 6 x 12 = 8 x 9. The only divisor of a number that is not paired with a different number is a divisor that is a square root. Consequently, all nonsquares have an even number of divisors, and all squares have an odd number of divisors.

How does this apply to the row of cards? Consider the eight of spades in the first card-turning example. Since 8 is not a square, it has an even number of divisors: 1, 2, 4 , 8 . It will be turned four times: when you turn each card, each second card, each fourth card, and each eighth card. An even number of turns applied to a face-down card will leave that card face down. Since every nonsquare card will be turned an even number of times, it will be face down at the finish. The only cards that are turned an odd number of times and left face up are those with an odd number of divisors, namely the squares. Is there a better way to teach this basic number theorem in the memory of a high-school student than to have him witness such a demonstration?
Don't forget there is still time to Celebrate the Mind—his and yours!—in 2011, with card or other entertainments. Have fun!

A Call For A New Shuffle Principle (Need Rot Sextet?)

On this August occasion, to mark the completion of seven years of Card Colms, we break with tradition and pose a question, rather than presenting some fresh mathematically based entertainments with cards.

It's a question that's been on our mind for a long time, and we'd really like to know the answer.
By a happy coincidence, this month's offering also marks our first foray into the new blog format for MAA columns, so that readers with ideas to contribute have the option of responding publically in comments below.

One, Two, Many

Humans reading this column may have noticed that for some in our tribe there are essentially three counting numbers: One, Two, Many. The last is certainly the most confusing–perhaps our inability to track three things at the same time when rushed is why we do poorly at Three Card Monte (including those versions with minimal sleight of hand).

In fact, it doesn't take much for us to lose track of even fewer objects, as tricksters of various shades have known for a long time. Paddle moves play with the brains of those of us foolish enough to think we know the difference between the two sides of an issue, and basic misdirection is all about getting people to take their eye of a single thing just long enough for the magician (or politician) to pull a fast one. There is rarely any need for smoke and mirrors.

This month's Card Colm asks a challenging question concerning the shuffling of more than two piles of cards. We may be asking too much.

Shove Integer

For those with a little knowledge of card shuffling, the following hypothetical exchange between two alphabetical sounding mathematicians, Aodh and Bea, may amuse:

Aodh: I've heard that seven shuffles is enough to randomize a standard deck of 52 cards.

Bea: I've heard that eight shuffles restores a standard deck of 52 cards to its original order.

This raises a tantalizing question: what magical thing happens between the seventh and eighth shuffle to restore total order from sheer chaos? That would be a very impressive effect in itself!

In fact, Aodh and Bea above are talking about rather different kinds of shuffles, though one generalizes the other.

The first statement has some validity when it refers to an irregular riffle shuffle, subject to some strong assumptions.

The second statement refers to a perfect shuffle, also known as "Faro" or "weave" shuffle, in which the deck is split in two at the middle, and the cards from the two halves are interlaced completely regularly, with the original top and bottom cards remaining in those positions (this is the so-called Out-Faro).

Riffle shuffling, in which the deck is split roughly in the middle, and the two resulting "halves" are interwoven by releasing cards from both thumbs at the same time, with no particular regularity, is a common way of mixing cards, being relatively easy to master.

A famous 1992 paper by Dave Bayer and Persi Diaconis called "Trailing the Dovetail Shuffle to its Lair" concluded that seven riffle shuffles is sufficient to randomize a standard deck. A specific measure of randomness was used, and assumptions were made about the probabilistic distribution of how the cards are split, and how the two resulting packets are "released."

Later on, others revisited this topic, with different measures of randomness and different probabilistic assumptions, reaching different conclusions. The topic continues to attract the attention of researchers, and today some argue that in fact eleven shuffles are required to really randomize a deck. This is not our concern here, so we leave it to the interested reader to pursue further, if desired.

Let's return to the idea of a single riffle shuffle, making no assumptions whatsoever about how likely the deck is to be split at or near the middle, or how regularly the cards from the two parts are dropped. All we assume is that the shuffle preserves the order of the cards within each "half": for instance, if one packet of red cards in a specific order is shuffled into another packet of black cards in a specific order, then both the red and black subsequences of the resulting shuffled deck should preserve their original orders.

Note that Lennart Green's rosette shuffle as depicted below is certainly a riffle shuffle, as we've mentioned here before. We should admit that this kind of shuffle has physical limitations governing the card mixing, so that not every possible riffle shuffle is actually achievable in this way.

[Start with two piles side by side, as shown in the first image, then use the fingers to "twirl" the left pile into a rosette; the second image shows the result. Repeat for the right pile, and then push the rosettes together. Square up the packet: it has effectively been riffle shuffled.]

It's a delightful surprise to learn that if we have a deck which

1. Starts out with the cards alternating red and black, and
2. Is split into two parts (of any size) one of which had a red card on the bottom, the other having a black card at the bottom,

then, if we subject it to a single riffle shuffle, it will end up with the property that every pair taken off the top (or bottom) will consist of one red and one black card, in some order. This is the so-called First Gilbreath Principle from 1958.

It's not hard to see that condition 2 above can be replaced with either of two alternatives: (2A) First dealing out some cards from the deck into a pile to form the second packet, instead of splitting as before, before shuffling, or, (2B) Splitting anywhere and shuffling, but then peeking at the card faces and cutting between two cards of like colour before peeling off pairs of cards.

This generalizes from cycles of length 2 to arbitrary n general as follows:

Start out with a deck of cards cycling in some regular fashion, for instance for n = 13 we might have 4 stacked repeats of these cards in (alphabetical) order: Ace, 8, 5, 4, Jack, King, 9, Queen, 7, 6, 10, 3, 2 (ignoring suits).

If some of the cards are dealt into a pile, thus reversing their order, and the resulting two packets are riffle (or rosette) shuffled together, then, we end with a deck with the property that the top (or bottom) 13 cards contain one of each value. This is the so-called Second Gilbreath Principle from 1966.

For Auto

Faro shuffling, in which the deck is split exactly in the middle, and the resulting half packets are perfected interlaced, is much, much harder to do in practice. [The key word here is practice–having once been shown for a solid hour "how to do it", by magician Mark Setteducati, a month's worth of frustrating and seemingly pointless practice suddenly led to an irreversible breakthrough.] If the top and bottom cards always remain in position—so that we are doing an Out Faro—it is well known that exactly eight such perfect shuffles restores a deck of 52 cards to its original order.

A great deal of impressive card magic has been developed by those who've mastered Faro shuffling, some of which can be adapted to the easy-to-handle inverse operation of dealing cards into two piles alternately. A great deal indeed!

S. Brent Morris has a terrific book Magic Tricks, Card Shuffling, and Dynamic Computer Memories from 1998 which not only surveys all of the key mathematics of such Faro shuffles, but also explores the mathematics resulting from three packets being perfectly interlaced (and he gives advice on how to do that in practice).
There is a question begging to be asked here.

Restores Teeth

Since a Faro shuffle is a special case of a riffle shuffle—the neatest possible type—it follows that anything promised by the Gilbreath principles will also hold for a deck which has been Faro shuffled, with bells on.

This brings us to our burning question (brusque intoning):

Is there a way to pre-arrange a deck and split it into three (or more) parts
so that some structure remains when they are "riffle shuffled" together?
Perhaps, following Lennart Green, a triple rosette shuffle of some sort can be executed on three parts of a deck so that the result is not totally chaotic? What kind of pre-arrangement would be required?

Bear in mind that card reversal of one packet is not required when riffle shuffling a pre-arranged deck in the usual way, in order ro retain some predictability, as we saw here two years ago in The Bligreath Principle.

If periodic cycling of some sort is appropriate—as it is in the case of splitting the deck into two packets before riffling—would the cycle length need to be a multiple of six? It seems that we must cover the case where two of the parts are riffled in the usual way and the third is merely appended at the top or bottom, which leads us to suspect that the cycle length must include factors of 2 and 3.

Most importantly, is there any hope of finding an application to card magic?

Or is it simply a case of one too many packets to shuffle?

We'd love to hear from readers with ideas on this topic. Please feel free to use the comment option below.

"Need rot sextet" is an anagram for "extend rosette," "shove integer" is an anagram for "seven or eight," "for auto" is an anagram for "out faro," "restores teeth" is an anagram for "three rosettes," and "brusque intoning" is an anagram for "burning question."