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:
Several questions arise:
The answers to two of those three questions is yes! Consider "Thy Array Clue":
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:
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."
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."
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):
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:
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.
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:
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.