Home Site Map Search :: Bitwise Courses :: Bitwise Dusty Archives

 Learn Aikido in North Devon

Section :: Wilf’s Mathematical Digressions

Format For Printing...

# Garden of Gilbreath

This month Wilf conjures with a mathematical mystery of magic...
Monday 5 June 2006.

Some years ago a quite astonishing observation about things taken in order was noted and exploited for fun in various conjuring tricks: one early investigator into this phenomenon was the famed stage magician Karl Fulves.

Within a few years the observation was analysed and documented by Norman Gilbreath, famed for his mathematical analysis of “semi-ordered systems” for the RAND Corporation. Gilbreath is also an avid conjuror, noted for creating some classic illusions of “magic”. This combination of interests is not so unusual when you realise that a deck of playing cards is itself an ideal model of a semi-ordered system.

Imagine you have two tubes, each of which can contain snugly a stack of draughts (or chequers). When you tip a piece out of either tube, only the one at the top of its stack can drop out, leaving the piece below it as the new top.

You tip out from these tubes exactly two pieces – it doesn’t matter whether or not they come from the same tube. When you look at them you find that one piece is black, and the other red. Imagine now that I prepared the tubes in advance, and told you at the outset that you would end up with one black and one red: how could I have prepared the tubes in order to be able to predict this outcome?

No matter how you select two pieces, one will be red and the other black

It’s not as difficult as you may think! In tube A the top two pieces must be coloured one black and the other red to ensure that if you took both pieces from tube A, you would get the predicted outcome; the same must be true of tube B. Additionally, the top piece in each tube must be of different colour in case I choose one from each. Say the top two pieces in tube A were black, then red (black topmost). Then the top two pieces in tube B must be red, then black. I can make four draws:

1. one from tube A, the other from tube B. this results in one black, the other red

2. one from tube B, the other from tube A. Result: one red, the other black

3. both from tube A. Result: one black, the other red

4. both from tube B. Result: one red, the other black.

That may be cute, but hardly earth shattering. Maybe it could be adapted into a bar-room trick and garner you a free half pint one day. But consider what is left. If the two pieces are taken one each from the tubes, you are let with one tube topped with a red piece and the other with a black piece. The tubes are reversed now, but from the top appear as they did before. If we arrange it so that a third piece were in each tube, we could presumably repeat the trick. This reasoning also applies if both pieces came from the same tube: if instead of emptying it, there were a third piece, we can be set for a repeat of the trick. So with pieces black, red, black in tube A and red, black, red in tube B any way of choosing a pair of pieces will result in one red and the other black.

As a matter of fact, you should now be able to see that the trick can go on endlessly: if both tubes have contents of alternating colours, but one starts with red and the other starts with black uppermost, you can continue to pick black/red (or red/black) pairs all day long. After each choice of two pieces – however made – you will be left with one tube having black at its top, and the other having red.

Now let’s take a radical step and merge the two tubes into one. Tube A had pieces alternating black/red/black/red, and tube B had pieces alternating red/black/red/black. Our new “supertube” will contain only black and red pieces. All of the pieces from tube A will still be in alternating sequence with each other, and all those from tube B will also be in alternating sequence: it is simply that in the “supertube” we lose account of from which tube each piece originally came. But think about it: the whole point of the little trick was that it didn’t matter from which tube you drew the pieces! Similarly it doesn’t matter now that the two stacks of pieces have been merged into one! Though there are now places in the stack where two consecutive piece have the same colour, taking two pieces at a time one will be black and the other red – guaranteed.

What’s more you can extend the trick in a new direction by introducing more colours. Among the remains of an old board game I found plastic counters of four different colours, and set up two stacks so that drawing four counters in any way would give me a handful of all different colours: one tube has the colours alternating black/red/yellow/green and the other in reverse: green/yellow/red/black. When I draw a counter from one stack, the next three counters from both stacks will sport the other three colours. Whichever stack I choose next, both stacks will afterward have the remaining two colours on top, and so on. There is no assurance that each set of four counters will have the colours in any particular sequence, but they will all be different colours.

I have included a Just BASIC source program (you can download the source code at the bottom of this article) which tries all combinations possible of taking four counters from two tubes. You can inspect the logic for yourself in the Just BASIC source file, Gilbreath01.bas, available for download from here. (You can also download and use the Just BASIC language at no cost whatever from www.justbasic.com).

Illusionist Max Maven calls the Gilbreath principle “a thing of terrifying beauty”, and employs it in novel ways in some illusions he has created. In one it forms the climax of a the trick when he ends up with two small piles of envelopes, seemingly disordered. At random onlookers select envelopes to form pairs. The audience thinks all the envelopes are different, but in fact they are of only two types. Their order in the two piles guarantees, by the Gilbreath Principle, that when the cards are divided into pairs, one of each type will occur in each pair. From this point, his complex trick runs to a successful conclusion automatically. This is exactly equivalent to our original investigation of two tubes filled with alternating black and red pieces.

It is a surprising but genius step to take, realising that choosing randomly from two tubes is exactly equivalent to choosing sets from a single tube (with the contents of the two tubes merged).

Physically merging the contents of two tubes can be modelled with playing cards: two piles of cards pushed together is a “riffle shuffle”. In an ideal riffle shuffle, a person takes two piles of cards (roughly the same size) and holds distant corners of one pile with fingers of the left hand, and distant corners of the other pile with fingers of the right hand. Bringing them close together at a corner the fingers apply a torque and flick cards downward alternately by each hand, corners from both piles overlapping. The effect is quite decorative, and the moving cards make a gentle rattle as the two piles combine. With skill and sufficient practice, a performer may be able to riffle shuffle so that cards in the merged pack alternate exactly from each of the two piles, but that is not necessary for the Gilbreath Principle: it still works, so long as the order in the original piles is preserved.

The riffle shuffle is not as effective as you may think with regard to randomising the order of playing cards

We have seen that the Gilbreath Principle works with four colours as readily as with two. It actually works for ANY number. Suppose you have two identical full decks of cards: one is in any order at all, while the other is exactly the same but in reverse order. Now riffle shuffle the two decks together, and then gasp aloud at your “error”. Calmly count off the first fifty-two cards and say “I hope that sorts it out”. Your onlookers are not likely to believe that Gilbreath’ principle will guarantee that the top 52 cards will all be different.

Another way of working the same trick is to keep the two decks separate, then throw a single die. If 2 is thrown, pick two cards from a pile. Throw again and pick the indicated number of cards from the other deck. Back and forth you go, picking cards from the two decks alternately until one of the decks is exhausted. Then pick up the remainder from the other deck. You have now picked up all 104 cards. Count out 52 cards, and announce that the two stacks are now properly restored to two separate decks. Somebody checks, and confirms that amazing claim as factual. The Just BASIC program Gilbreath02.bas illustrates these examples.

Can you shuffle together two decks of playing cards – and then instantly separate out 52 different cards?

There is another side to the Gilbreath principle that is, in its way, even more amazing. What we have observed at up to now is what happens when two piles are merged with one of them specially reversed. But Gilbreath observed that even when the two piles have order in the same “direction” there is an inherent pattern not lost by a riffle shuffle or merge. This new trick’s effect is more surprising with an odd number of ways objects can be ordered, so we shall demonstrate it with a deck of cards cut down to THREE suits. Take out all the clubs from a deck, and arrange the remaining 39 cards in triplets each containing one spade, one heart and one diamond – in that order. The shortened deck turned face down should have a SPADE on top. Now cut the cards into two piles of roughly the same size. The bottom card from the pile made up from the bottom of the deck will be a diamond, but you must note the suit of the card at the bottom of the other pile, created by the cut. It may be spade, heart or diamond. Merge the two piles into one (riffle shuffle or equivalent, again!) and count off triplets. Some triplets are likely to have one of each suit, but in other triplets a suit will appear twice. The results should surprise you:

You will never find a triplet all of the same suit.
There will be an EVEN number of triplets with a pair of the same suit.
If a spade appears at the bottom of the cut pile, those triplets with pairs the same suit will vary between hearts and diamonds for those suits.
If a heart appears at the bottom of the cut pile, those triplets with pairs the same suit will vary between spades and hearts for those suits.
If a diamond appears at the bottom of the cut pile, those triplets with pairs the same suit will vary between spades and diamonds for those suits.

Suppose a heart appears at the bottom of the new (cut) pile: after shuffling and taking cards three at a time, I may find a pair of spades, and then before long, I know that a pair of hearts will appear. Another pairing may come up, and it will be spades again – then hearts again.

The program Gilbreath03.bas illustrates this.

You can download all the program code needed to test of the Gilbreath principle and run them using the free Just BASIC system

There you have it: the Gilbreath Principle, astounding in its implication, broad in its application, yet seemingly confined to the world of conjuring tricks and bar-room bets and challenges. The beauty of Numerical Analysis is that the story is not necessarily finished. This principle may yet find a practical application that changes our lives in wonderful ways.

Source Code

Wilf’s Just BASIC programs demonstrating the Gilbreath Principle

2.8 kb

Home