Let's start with an item from page 154 of Martin Gardner Presents (Kaufman
and Greenberg, 1993), originally published in Octet by Karl Fulves (1981),
which seems to have started life as a blackboard puzzle in a Russian high school
science magazine called Quant.
Hand out for shuffling a packet containing an even number of cards, say ten,
where some are face down and others are face up. Ask a spectator to take off
pairs of cards from the top, and replace each pair with a single card according
to the following rules: if the cards are facing the same way, set them aside and
replace with a single face down card; otherwise replace with a single face up
card. The first pair is replaced with a card as indicated, then this card and
the original third card are processed, and so on, until some card is processed
along with the original bottom card, so that finally just one card remains.
One way to summarize the replacement rules is given in this table:
DD
D
DU'r'UD
U
UU
D
Several questions arise:
Can one predict in advance whether that last card will be face up or face down?
Does it matter what the initial packet size is?
Could the cards be shuffled along the way, so that the final comparison
does not always include the original bottom card?
The answers to two of those three questions is yes!
Consider "Thy Array Clue":
1st\2nd
D
U
D
D
U
U
U
D
That was a relevant anagram for a recasting of the replacement rules--it's
the (Arthur) Cayley table for any two-element group (with D as the neutral
element). It's more recognizable as:
1st\2nd
0
1
0
0
1
1
1
0
Entries are combined according to the rule "add mod 2": the point being that
1 + 1 = 0 here. This is equivalent to the observation that the sum of two
numbers of like parity (both even or both odd) is even, whereas the sum of
two numbers of different parity (one even and one odd) is odd.
We can now see that the act of weighing up each pair of cards to decide what
single card to use instead boils down to "addition mod 2," where D plays the role
of 0 and U plays the role of 1. Since addition mod 2 is known to be associative
and commutative, we see that for a given packet of cards, in various up/down
orientations, it makes no difference what order they are combined in. The
entire exercise is just addition mod 2 of all of the numbers (0 or 1)
corresponding to the cards used. Hence, the outcome is very predictable: it
depends only on how many face up cards were in the packet to begin with; we'll
end up with a face down card precisely when we start with an even number of
face up cards. The answers to the questions above are: Yes, No and Yes--and
"Thy Array Clue" is an anagram of "Arthur Cayley."
Brainy Span
Have a spectator shuffle a deck and discard about half of it. Take approximately
a third of what remains, giving the rest to the spectator, and suggest that each
of you scans your card faces to ensure that they are totally random. Secretly
count your cards; suppose you have 11. Ask the spectator to turn their cards
face up and riffle shuffle them into your cards face down. Say that you have
no idea how many cards are face up or face down, or how they are arranged; this
is mostly true. Shuffle further, and hold the cards fanned, out of sight, e.g.,
under a table, asking the spectator to blindly remove any 11 cards to form a new
packet. Close the fan and bring the rest of your cards forward, flipping the
packet over while it is still out of sight.
Thanks to a Martin Gardner extension of an old Bob Hummer principle, your packet
and the spectator's now have the same number of face up cards. Hence, if each
packet is processed according to the rules above, the final cards in each will
match in orientation (both face up or both face down): this you can predict ahead
with absolute certainty. "Brainy Span" is an anagram of "Binary Snap."
Tremor Hit the Deck
Hand out for shuffling about a quarter to a third of the deck, where some cards
are face down and others are face up. Joke that a tremor hit the deck and the
cards ended up really jumbled. Ask a spectator to take off pairs from the top
successively, and replace each with a single card according to these new rules:
if the cards are face up and the same colour, set them aside and substitute a
single face up card of the opposite colour; if the cards are face up and of
different colours, set them aside and substitute a single face down card; if the
cards are facing opposite ways, simply set aside the face down card and retain
the other; otherwise both cards are face down, set one aside and retain one.
Have the whole packet processed in pairs until one card remains.
Similar questions arise (and they have the same answers):
Can one predict in advance whether that last card will be face up red or
black, or face down?
Does it matter what the initial packet size is?
Could the cards be shuffled along the way, so that the final comparison
does not always include the original bottom card?
Denote face down cards by 0, face up blacks by 1, and face up reds by 2.
Here are tables of the new replacement rules, both as cards and as numbers:
1st\2nd
D
B
R
D
D
B
R
B
B
R
D
R
R
D
B
1st\2nd
0
1
2
0
0
1
2
1
1
2
0
2
2
0
1
These are two manifestations of the Cayley table for a three-element group (with
D as the neutral element). Entries in the second are combined according to the
rule "add mod 3," so that 1 + 2 = 0 and 2 + 2 = 1. Since addition mod 3 is
associative and commutative, the outcome is predictable, depending only on how
many face up cards of each colour are in the packet to begin with. (Face down
cards contribute nothing to the sum mod 3, so it doesn't matter how many you
start with.)
For example, suppose there are five face up Blacks and three face up Reds at the
outset: since Reds and Blacks cancel, the upshot is two dominating Blacks, which
yields a face up Red as the final card. In general, the final card is determined
by the excess number k of the dominant colour. The final card is the same
colour as the dominant one if k is congruent to 1 mod 3, is the opposite
colour if k is congruent to 2 mod 3, and is face down otherwise. Jeff
Ehme suggests that if 2 is replaced with -1 (a well-known alternative way of
denoting this element of this small group), then the similar roles of Red and
Black becomes clearer. This also ties in nicely with the colour switching
referred to in the previous sentence. "Tremor Hit the Deck" is an anagram of
"The Mod Three Trick" (incidentally, "I Mortar the Deck" bears the same
relationship to "A Mod Three Trick").
We can generalize further along these lines, to cards naturally grouped into
4, 5 or even 6 sets, but it's hard to explain the replacement rules without
basically defining addition mod n. Let's try for something a little
different.
The Heftiest Subtotal
Start by removing a few cards of each suit and forming four neat face up piles
of these on the table. Have a spectator shuffle the remainder of the deck, and
split it into two parts. Take one part back, and look through the card faces,
inviting the spectator to do likewise with the other part, to ensure that the
cards are thoroughly mixed. Invite further shuffling on the spectator's part,
and shuffle your own cards also. Write down two predictions and have them set
aside.
Explain that each of you will go through your cards, two at a time, using the
piles on the table to replace each pair with a card according to the rules below,
until just one "winner" card remains. Shuffling can be done along the way.
Here are the rules of engagement: If both cards have the same suit, replace them
by a Diamond; if exactly one card is a Diamond, replace the pair with a card
whose suit matches the other card; otherwise the two cards represent two of
the three suits Clubs, Hearts and Spades, in which case replace them with a card
of the suit omitted.
Demonstrate by processing your pile first, placing discarded cards to the side.
When you arrive at your winning card, leave it on display, and then guide the
spectator through the processing of the other pile until there is a second
winning card. Open your predictions to confirm your foresightedness.
Here is a table of these replacement rules:
1st\2nd
D
C
H
S
D
D
C
H
S
C
C
D
S
H
H
H
S
D
C
S
S
H
C
D
That's the Cayley table for the Klein-4 group, a non-cyclic little four-element
group (with Diamonds playing the role of the neutral element)! Weighing up pairs
of cards (to decide which card to replace them with) boils down to "addition" in
this group, which is also associative and commutative. Once again, the outcome
is predictable, depending only on how many cards of each suit (ignoring Diamonds)
are used. Shuffling at any stage is permissible.
Since you control how many cards of each suit are used in the replacement piles
at the outset, and you get to scan your own cards, you can determine how many
cards of each suit you both have. Actually, all like pairs are converted into
Diamonds, which in turn do not alter the suit of any card they are compared to,
so all you need to know for each of the "non-trivial" suits Clubs, Hearts and
Spades is which of you has an odd number of these.
For instance, if you have an odd number of just one suit, then that suit will
prevail, and if you have an odd number of each of Clubs, Hearts and Spades, then
the final card will be a Diamond. If you have an odd number of exactly two suits
(e.g., Clubs and Spades), then pairs of these turn into Diamonds, leaving one of
each left, which results in the third suit (a Heart in our example) as the final
card. Thus the winner of the "battle of the suits" (an anagram of "heftiest
subtotal") is pre-determined.
There are ways to guarantee having sufficient information about who has how many
(mod 2) of each suit without having to scan about half of the cards used. For
instance, start with a deck whose suits cycle CHaSeD (Clubs, Hearts, Spades,
Diamonds) and ask that a number between 15 and 25 be called out as you repeatedly
cut the cards. Count out that many cards face down, thus reversing their order,
and invite the spectator to riffle shuffle the resulting piles. While you turn
your back, ask that the called-out number of cards be dealt to the table, face-up
this time. Stress how you couldn't know anything about the order of the cards at
this stage; actually you do for two reasons. By the so-called
Second Gilbreath Principle, you know that after the riffle shuffle, each clump
of four cards from the top (or bottom) of the packet has one representative of
each suit. If the number then counted out is a multiple of four, do nothing;
have the cards counted out and flipped face-up again ready for Ein Klein
Quantified Reasoning (this time you predict a Diamond). If the number
counted out is one more than a multiple of four, merely peek at the last card
dealt before having the cards flipped face-up (and predict that suit). If the
number counted out is two or three more than a multiple of four, you'll need to
take the cards back and fan slightly, face up, to peek at the last two or three
dealt (and adjust your prediction accordingly).
Throughout we've suggested that pairs of cards be pulled directly off the top (or
bottom--we're sometimes vague about whether the packets used are face down or
face up). Another option in every case, which takes advantage of associativity,
is to remove pairs of cards (adjacent or not) from anywhere in the packet, and
replace them with single cards according to the rules of the game. All tables
above are symmetric across the principle diagonal running NW to SE: that's the
commutative (Abelian) property.
Since 1988, Colm Mulcahy (colm@spelman.edu)
has been in the department of mathematics at Spelman College, where a recent
project of his was the creation and launching of the new
BIO SIGMAA webpage.
He is pleased to have found a context in which one can say "shuffling is
commutative." For more on mathematical card tricks, see
http://www5.spelman.edu/~colm/cards.html.
