Card Colm
(by Colm Mulcahy)

October 2008

Monge Shuffle Cliques

The Monge shuffle is a special way of mixing a packet of cards, which may give the impression of randomization if done sufficiently often. It's named after Gaspard Monge (1746--1818), the founder of descriptive geometry, whose interest in it was piqued two centuries ago. For the sake of explanation we assume at first that the cards are arranged Ace, 2, 3, ..., from the top, and are face-up; in practice they'd generally be face-down. The cards--typically no more than a third of a deck--are passed from one hand to the other, one at a time, so that the even-numbered cards pile up in front of the Ace, and the odd-numbered cards behind it.

For instance, starting with Ace, 2, 3, ..., 10, we end up with 10, 8, 6, 4, 2, Ace, 3, 5, 7, 9; whereas starting with Ace, 2, 3, ..., 10, Jack, we end up with 10, 8, 6, 4, 2, Ace, 3, 5, 7, 9, Jack. Notice how in the second case, the original bottom card ends up at the bottom again, and the rest end up in the same positions they did in the first case, which used one fewer card; these observations hold for any odd-sized packet, and mean that we really only need to study the shuffle on packets of even size.

We now describe a common way of performing this shuffle, in which the left thumb pushes off cards one at a time for the right thumb (and fingers) to alternatively collect at the bottom/front and top/back of an ever-growing newly-arranged stack. The right hand simultaneously moves up and down (or "in and out") to facilitate these pickups. In detail:

Hold the packet in the left hand, and with the right hand, thumb off the top card.
The right hand should now be lowered slightly relative to the left one, and then
promptly raised again to collect the second card (pushed off by the left thumb)
on top. Without hesitation the third card from the left hand is thumbed off and
collected under those already held in the right hand, which is immediately
lowered in preparation for taking the fourth card on top. In this way, with a
steady rhythm, the evens pile up on top of the first card, the odds underneath.

(Alternatively, one can keep the right hand relatively stationary during the transfers, and move the left hand "in and out" as it offers/deposits cards.)

Click on the image below to see a brief video of this in action.



(Here the cards are shown face-up, so one can see which one goes where, and also the fans displayed at the start and finish should be read from right to left.)

What interested Monge was the order or period of this shuffle, i.e., how many times it had to be applied to a packet to restore the cards to their original order. Apparently, Monge himself derived the kind of data in this table:

Number of cards 2 4 6 8 10 12 14 16 18 20 26 32 52
Period of shuffle 2 3 6 4 6 10 14 5 18 10 26 6 12


Magicians have taken advantage of some of this, e.g., the fact that four such shuffles, far from mixing a packet of eight cards, actually restores it to its original order. Few, however, would recommend inflicting twelve Monge shuffles of a whole deck on an audience just to cash in on the corresponding fact in that case.

There's a well-known relationship between a card's starting and ending positions, after one or more Monge shuffles, which can be found in Martin Kraitchik's book Mathematical Recreations (W. W. Norton, 1942). Recent work has been done on the permutation group determined by "The Monge Shuffle for Two-Power Decks" by Arne Ledet (Math. Scand. 98, 2006). Our explorations below are of a more elementary nature.

Coming Sequel

The periods listed above can be verified by examining the cycle decompositions of the permutations associated with the shuffle on the packets in question, since the period of any permutation is the least common multiple of the lengths of its constituent (disjoint) cycles. For packets of size n (up to 13), this information is contained in the next table.

n period cycle decomposition fixed points
2 2 (1 2) -
3 2 (1 2) 3
4 3 (1 3 4) 2
5 3 (1 3 4) 2, 5
6 6 (1 4 2 3 5 6) -
7 6 (1 4 2 3 5 6) 7
8 4 (1 5 7 8) (2 4 3 6) -
9 4 (1 5 7 8) (2 4 3 6) 9
10 6 (1 6 3 7 9 10) (2 5 8) 4
11 6 (1 6 3 7 9 10) (2 5 8) 4, 11
12 10 (1 7 10 2 6 4 5 9 11 12) (3 8) -
13 10 (1 7 10 2 6 4 5 9 11 12) (3 8) 13

We also list the fixed points, i.e., the positions of those cards which end up where they started. As previously noted, this includes the last card for packets of odd size. For instance, for n = 5, the fact that Ace, 2, 3, 4, 5, become 4, 2, Ace, 3, 5, under a single Monge shuffle is equivalent to noting that overall the 2 and 5 do not move, and the presence of the 3-cycle (1 3 4) means that the Ace moves to position 3, the 3 to position 4, and the 4 back to position 1. Two more applications of the Monge shuffle ot this packet restore the it to its original order. For n = 10, the 4 stays where is it, the 2, 5 and 8 cycle around (the 2 moving to position 5, the 5 to position 8, and finally the 8 back to position 2), and independently the Ace, 6, 3, 7, 9 and 10 cycle around in a like manner. Because 3 and 6 (the lengths of the two disjoint cycles here) have least common multiple 6, it follows that five more applications of the Monge shuffle restore a packet of ten cards to its original order.

We suggest focussing on cliques, i.e., small collections of cards which are invariant as sets under arbitrary (unknown) numbers of Monge shuffles, such as modestly-sized unions of fixed points, transpositions (2-cycles), 3-cycles, or 4-cycles. Mostly, we explore magic options for packets of ten cards.

Four Play

For starters, have the deck shuffled and ten or eleven cards counted out into a pile. One of those cards is chosen and looked at by a spectator. Have it put back into a face-down spread of the remaining cards; it's essential to note silently exactly which position it now occupies. Cut the packet several times, moving clumps of three to five cards from top to bottom, so that the chosen card ends up fourth from the top. Perform a Monge shuffle or two, and once it's clear that everybody understands how this is done, invite others to do additional Monge shuffles while you turn away.

Ask for a number less than ten to be called out; suppose "Eight" is the result. Turn around again and ask for the packet, which you now hide behind your back. Announce, "I'm going to move the selected card to the eighth position, which is quite tricky, as I have no idea what that card is." While your claim is largely true, you do in fact know that the selected card is still in the fourth position, so simply move four cards from bottom to top, and you are set for a successful conclusion. Have a spectator count out to eight, while dealing cards to the table; the last one dealt is indeed the desired selection.

Better Poker Hands With Gaspard Monge

Have a deck of cards thoroughly shuffled by a spectator, and ten cards randomly selected face-down and handed to you. Glance at their faces quickly and casually mix them, while commenting that you are going to let the spectator mix them even more before determining two poker hands, one for each of you.

Explain and demonstrate the Monge shuffle a few times, before handing the packet to the spectator, inviting him to apply the shuffle as often as he wishes, while you turn away. At the conclusion of this shuffling, turn back. Announce, "These randomly selected cards are now really well mixed. Let's try something, please move cards from the top to the bottom, one at a time, and one for each letter in the words of the following phrase. After each word is spelled out, set the next card aside. The phase is `A poker hand worth keeping,' are you ready?"

The top card is transferred to the bottom by the spectator, as he says, "A", and the next card set aside. Then five cards are moved from top to bottom, one at a time, as "poker" is spelled out. The next card is set aside. The spectator continues, spelling out "hand," "worth," and "keeping" in turn, and setting aside three more cards. Take the remaining five cards for yourself, and comment, "You have selected five cards for yourself; I get the ones that remain. Let's compare our cards as poker hands. Look at your cards now, and I'll look at mine." The spectator should be pleased to discover that he has the winning hand. You can conclude by adding, "I guess that really was a poker hand worth keeping!"

This effect combines earlier observations about Monge shuffles on packets of 10 cards with the fact that given ten random cards, there is a high probability (98% in fact) of getting at least one pair, as shown in Better Poker Hands Guaranteed (the June 2006 Card Colm). There the focus was on different ways to ensure that one of two players ended up with the winning poker hand, i.e., containing the almost certainly occurring matching pair or better. Here, you must ensure that during the initial mixing, when you have glanced at the card faces, there are four winning cards---that's as many as you can control the positions of---second, fourth, fifth and eighth from the top. This can be achieved by means of casually rearranging clumps of cards in your hand, while blathering about future mixing and randomly selected poker hands. Turn the packet face-down before explaining and demonstrating Monge shuffling. Then hand the cards to the spectator as you turn away.

Because the cycle (2 5 8) occurs in the decomposition of the Monge shuffle on ten cards, considered as a permutation, the cards that start in those three positions will remain in them, possibly in a jumbled order, no matter how many times the spectator applies the shuffle. Moreover, since position 4 is a fixed point, the card that starts fourth from the top is there again after each shuffle. The upshot is that the four desired cards are in the same four positions, although three of them may well be in a different order than they were at the outset.

When you turn back, and have the spectator spell out "A" and deal the next card, this results in the card in the second position being set aside. Spelling out "poker" and dealing the next card results in the eighth card being set aside. The next spelling ("hand") sees the (invariant) fourth card set aside, spelling "worth" results in the irrelevant first card (which certainly can't hurt the value of the spectator's poker hand) being set aside, and finally, spelling "keeping" sees the original fifth card complete the spectator's poker hand, as desired.

Of course one often gets more than a single pair among ten randomly selected cards. If two pairs show up, make sure they are the cards planted in the four key positions. If a pair (or two) and three of a kind show up, make sure that the three of a kind go to the spectator. Similar adjustments are made if even better cards are among the ten being used. In the rare cases where there is nothing at all of interest in the ten cards, throw them down in disgust, face-up, and ask for ten new ones, commenting that you're trying to help the spectator get a winning hand and you need something to work with.

Four Red Faces

A much simpler application of Monge shuffling is to first stack the deck so that among the top ten cards, the third, sixth, seventh and ninth from the top are red-faced, and the other six are black-faced. In the usual way, some convincing looking riffle shuffling can be done casually while maintaining this top stock, before dealing out ten cards in a pile, thus reversing their order. Now, it's the cards in positions 2, 4, 5 and 8 that are red. Hand out the pile of cards and encourage plenty of Monge shuffling, having first demonstrated, as before.

Have a spectator deal the packet into a face-up pile, and announce that you are going to try to guess the colour of each card right before it is dealt. Since it's still true that the second, fourth, fifth and eighth cards are red---this clique was actually a feature of the earlier video demonstration of the Monge shuffle---you can get as many of these "guesses" correct as you wish. It's fun to have the spectator guess also, and the odd error on your part actually throws people off the scent.

Incidentally, our title will carry a little extra weight if the four red cards used are selected from the six red royal cards, perhaps with the addition of a suitable storyline.

Another possibility is to do a version of this where you forget reds and blacks, and instead guess which card values are prime, or odd, or Fibonacci numbers.

One, Two, Three, Final: Four Aces

Another option is to start as above, but with the four Aces in those positions (2, 4, 5, 8) which form a clique for a packet of size ten. After a spectator has been given ample opportunity to mix the cards further using Monge shuffles, take the packet back and spell out "Ace"---moving one card from top to bottom for each letter---before dealing the next card face-down to the table. Repeat twice more, using the same word "Ace," dealing two more cards. Curiously, three Aces are now on the table, and seven cards remain in your hand, the second of which is the last Ace. Spelling eight letters will yield that final Ace in a similar way; and the possibilities include "four aces," "fourth is," or indeed, "final ace." You can wait till all four cards have been extracted to reveal their identities, or you can expose them one by one (or three, then one) for dramatic effect.

The word sequence "One, Two, Three, Final" also does the trick.

Shorthand Keeper

Our table of cliques above stopped at n = 13 for a reason. The periods for n = 14 and 18 are 14 and 18 respectively, as already noted in the earlier periodic table, corresponding to single cycles of those lengths. It's more interesting for n = 16: the cycle decomposition is (1 9 13 15 16) (2 8 5 11 14) (3 10 4 7 12), with 6 being fixed. This suggests the possibility of controlling three poker hands at the same time, if appropriate word spelling sequences are planned. The one additional card---whether you take advantage of its fixed position or not---can be dressed up as a good luck card, e.g., used to tap the winning hand before it is revealed to all. Focussing on just one good poker hand is not such a bad idea, as only one spelling sequence really needs to be worried about: for the other two hands, let the cards fall where they may.

Scheming Two

A Monge shuffle on a packet of size twelve switches the cards in positions three and eight, as well as shunting the remaining cards around in a 10-cycle. (A full suit can be accommodated too; everything just said holds for the first twelve cards, while the last one effectively never moves.) This observation can be used in situations where two cards are randomly selected by different spectators from a fan of twelve or thirteen (not necessarily of one suit), and they are then reinserted in positions 3 and 8. Monge shuffling follows, to no avail: the two selections are easy to tease out in various ways, with or without spelling. If you happen to know the parity of the number of shuffles performed, you can also tap into the concept of switched selections, another magic staple.

Some readers may wish to seek applications of the case n = 22 (with period 10), which involves a transposition, a 3-cycle and a 4-cycle.


Colm Mulcahy (colm@spelman.edu) completed his PhD at Cornell in 1985, under Alex F.T.W. Rosenberg. He has been in the department of mathematics at Spelman College since 1988, and writing Card Colms---the only MAA columns to actively encourage lying on a regular basis---bi-monthly since October 2004. For more on mathematical card tricks, including a guide to topics explored in previous Card Colms, see http://www5.spelman.edu/~colm/cards.html.

"Coming sequel" is an anagram of "Monge cliques," "shorthand keeper" is an anagram of "three poker hands," and "scheming two" is an anagram of "Monge switch."

Video credit: Molly Mulcahy.

Past Columns



Past Columns