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