# The First Norman Invasion

August 2005

History tells us that the first Norman invasion of Ireland commenced in 1169. It seems unlikely that any of the invaders took the time to dwell on the possibilities inherent in riffle shuffling a pre-arranged deck of cards. That came 789 years later, a continent away, in more peaceful times. But that too was a kind of Norman invasion — in this case, of a stimulating new idea into the world of card magic.

Riffle shuffling a deck of cards refers to dividing it into two (not necessarily equal) packets, and then dovetailing those together — perhaps using the thumbs to release the cards — with no particular regularity. This type of shuffling is often thought to help randomize a deck, yet a single riffle shuffle can lead to some quite predictable results. It can be used to "reveal" some surprising mathematics, which we explore below.

## The Density of Primes

"For this trick I need three volunteers, which is quite a coincidence, as 3 is the first odd prime, and this is all about prime numbers, oddly enough." As you speak, you should casually do several overhand shuffles of the type which merely cycle the cards around. The first volunteer is handed the deck and asked to perform a riffle shuffle. Take the cards back and fan them towards the audience, stressing the random ordering present, commenting, "I forgot to mention that it's important that all volunteers can tell at a glance if a number is prime or not, I hope that's not a problem." Place the deck out of view, either under a table (if you are seated) or behind your back.

"In mathematics we often prove that two sets have the same size by establishing a one-to-one correspondence between them, that's exactly what we are about to do now. It is popularly believed that there are more composite numbers than primes, but we claim that on the contrary, exactly half of the numbers are primes. Jacks and Kings are primes of course, having values 11 and 13 respectively, and Queens are composites, since they count as 12."

Slowly bring forward pairs of cards, one by one, as if you were doing some difficult mental (and/or physical) gymnastics before making each selection. Hand them to a second volunteer, and ask that person to confirm that each pair consists of one prime and one composite value. Bring forward several pairs like this, as you build up confidence. Nothing can go wrong. Stop when you have made your point; few audiences will want to see you run through all of the cards.

Conclude, "As you can see, we have found a natural one-to-one correspondence between the set of primes and the set of non-primes. Hence, the density of primes is exactly one half."

Finally turn to the third volunteer, "I know what you're thinking: there's some potential here. Perhaps some corollaries? Maybe, `The set of primes is finite'? Or a deep connection to the Riemann Hypothesis? Good luck!"

This trick is actually quite easy to do, thanks to two key facts. The first, which few realize, is that in our context the density of primes is one half: in a standard deck, the prime values are 2, 3, 5, 7, J, K, and the composites are 4, 6, 8, 9, 10, Q. Six of one, half a dozen of the other! Omit the Aces to cut down on arguments over whether 1 is prime or not...

The second key ingredient is that riffle shuffling isn't all it's cracked up to be. Karl Fulves has pointed out that early in the 20th century, O.C. Williams went public with the basic fact that a single irregular riffle shuffle falls far short of randomizing a deck of cards, contrary to most people's intuition. In the 1920s and 30s, this observation was expanded on by Charles Jordan, and in the late 1950s Norman Gilbreath and others rediscovered the principle and took it to new heights. It's the 1958 incarnation that we refer to as the First Norman Invasion; a more common appellation is the (First) Gilbreath Shuffle Principle. (Yes, there was a second one a few years later, which is actually a generalization of the first one. We'll explore that one here in 2006.)

Arrange the deck at the outset, to consist of alternating prime values and composite values, skipping the Aces. (This effect could, for instance, be done as the follow up to a four Aces trick). Casually fanned to the audience, no pattern will be obvious. Proceed as above, first overhand shuffling as mentioned to give the illusion of card mixing, before having a volunteer do a single riffle shuffle.

Take the cards back and fan once more, pausing at two adjacent cards which are either both prime or both composite, as you comment on how jumbled the deck now is. Here's the secret: cut the deck between these two cards. It is essential that you end up with either primes at the top and bottom, or composites at the top and bottom; if this is the case when you get the cards back, no cutting is necessary.

Place the deck out of sight. If you merely take pairs off the top (or bottom) every time, then each will automatically consist of a prime value and a composite value. That's all there is to it!

This was initially conceived and performed using a more well-known division of the cards, into two like-sized packets: reds and blacks. Karl Fulves has it in his More Self-Working Card Tricks (Dover, 1984), where he remarks: "This routine was independently devised by Gene Finnell, Norman Gilbreath and others." Gilbreath's discovery was essentially this trick — and the title "Magnetic Colors" is his.

Why does it work every time? We provide an explanation at the end below, but recommend that readers first try to think it through for themselves. Simple, elegant expositions can be found in Chapter 9 of Martin Gardner's New Mathematical Diversions from Scientific American, which was originally published in 1966 (and is now available from the MAA), and in NG de Bruijn's "A riffle shuffle card trick and its relation to quasicrystal theory," Nieuw Archief Wiskunde (1987). (Gardner had first brought "Magnetic Colors" to the public's attention in his June 1960 Scientific American column.)

## Easy As $$\pi$$

"We're going to do an experiment here, and see if this deck of cards knows any mathematics. Can somebody get a pen and paper, please?" Overhand shuffle, and fan the cards, commenting that they are well mixed, some face up, others face down. Give them to a volunteer, who is invited to riffle shuffle. Take the cards back, fan them towards the audience again so that all can see how "random" they are, and then place them out of view.

Bring forward three pairs, in quick succession, and throw them on the table, noting, "Look, three pairs all facing the same way, amazing isn't it?" Then drop some cards on the floor, clumsily. Reprimand yourself, saying, "Too late now, we'll never know which way those were facing. Let's try again."

The next pair proves to consist of two cards facing different directions, which you comment on. Then you produce four pairs facing the same way. It's time to suggest that the second person keep track of these details on paper. Recap, "We started with three pairs facing the same way, then we got a pair facing opposite ways, then four more facing the same way. Write down 314 please." Continue, until three more numbers have been generated, namely one, five and nine. Have 159 written down beside the 314. Then step back, and gasp, "I don't believe it! Remember I dropped some cards after the first string of three pairs facing the same way? Let's put a marker, a period, after the 3 you wrote to denote that. Do you notice anything? Three point one four one five nine! It's as easy as π."

Actually, any numerical sequence, such as a house number or telephone number, can be spelled out in this trick. At the outset, the deck is arranged so that it alternates face-up and face-down cards. Casually fanned to the audience, clumps are likely to occur, and the arrangement will not be obvious. Proceed as above, this time cutting (if necessary), after the second fanning, to ensure that the top and bottom card are facing the same way.

With the cards hidden, take pairs off the top, one at a time. If brought forward as they are, all such pairs would consist of one face-up and one face-down card (in some order). By silently turning one of the cards over, you can convert any such pair to one whose cards face the same way. In this manner you can control the outcome for all pairs produced, to generate the digits of π or any desired number. The decimal point gag depends on your "clumsily" dropping an even number of cards, so as not to disturb the order that remains after the riffle shuffle.

This was inspired by "The Hustler" from Peter Duffie & Robin Robertson's Card Conspiracy Vol. 1 (Duffie & Robertson, 2003). The idea of using face-up and face-down cards in place of red and black in the Gilbreath context goes back as least as far as Nick Trost in 1964.

## Prime Locations

We wrap up with a simple item based on a principle which the Norman invaders of 1169 may well have conceived of, before they started marrying the locals and assimilating into the general population. The deck is shown to be well mixed, and is split between two people, who are encouraged to shuffle further. Each person now peeks at the top card of their pile and memorizes it, before exchanging cards and shuffling again. Finally, the two piles are recombined, and the cards cut several times. You take the deck back and fan it publicly, rapidly pulling out two cards and placing them face down on the table. Have the two selections named and the cards turned over.

This trick would be very easy to do if one person got all red cards and the other all black cards. The selected cards would break these runs in the reassembled-and-cut deck you look through. However, this would necessitate your being the only person who got to see the card faces. The prime and composite division used earlier, perhaps lumping in the Aces with one group just for the fun of it, removes the REDS factor (Risk of Embarrassment, Detection and Shame), should anyone glance at faces (yours or the cards').

This is based on "Double Location" from Scarne on Card Tricks (Crown, 1950) which uses even/odd cards. Like the separation we suggest, this yields slightly lopsided packets, of twenty-four and twenty-eight cards, respectively. Scarne credits the idea of proceeding from a colour-separated deck to a (single) location to Martin Gardner.

## Why it all works

(Based on de Bruijn's treatment of the first Gilbreath principle.) Let's go back to the original concept where the cards alternate red and black. There are two cases to consider, depending on whether the bottom card of the two packets being shuffled have opposite colours or not. In the second case, where both cards have the same colour, simply ignore one of them entirely, which means that the finished shuffled deck is "out of sync by one": taking off the bottom card of this shuffled deck will reduce to the first case, and cutting the deck between two like-coloured cards has an equivalent effect.

There are three things to keep track of: the initial two packets, held in the left and right hands, which we assume consist of alternating cards with bottom cards of different colours, and the stack of shuffled cards, which starts off empty. Consider the situation after the first two cards have fallen. If they both came from the same hand, then the stack of shuffled cards consist of a pair of oppositely coloured cards (in what order we cannot say), and the remaining left and right packets still alternate in colour with bottom cards of different colours. But the very same observation is true if the two fallen cards came from different hands! This argument continues to hold for each successive pair of fallen cards; hence the shuffled cards consists of unmatched pairs as claimed.

Norman Gilbreath lives in Los Angeles with his family and may be contacted through his web site yourmindtrip.com. On most Friday evenings, he may be found at Hollywood's Magic Castle, giving impromptu performances of his original creations.