Friday, August 29, 2014

Trim Hex Anagrams

As Martin Gardner fans new and old gear up to attend or host centennial Celebration of Mind events on or around 21 October 2014, including a special screening of long-lost video footage of the legendary mathematics popularizer—at the MAA Carriage House, Washington, DC—we add to the celebrations with another round of card considerations spawned by his always entertaining writing.

Between 1977 and 1986, Martin penned 111 "puzzle tales" for his friend Isaac Asimov's Science Fiction Magazine. They all resurfaced in three collections, the first and last of which are much more well known than the middle one. His words in the foreword to one of these books apply equally to all of them:
Each chapter poses a problem answered in the First Answers section. The solution in turn raises another problem that is solved in the Second Answers section. This may suggest a third question, and in several instances there is a fourth.... Many of the problems lead into nontrivial regions of mathematics and science.
As a result, a quick glance through any of these volumes soon suggests interesting things to explore with a deck of cards.
title       title

The first puzzle tale collection was Science Fiction Puzzle Tales (Potter, 1981), more familiar today in its MAA incarnation Mathematical Puzzle Tales from 2000. Just six months ago, "Postage Stamp Issue" (February 2014's Card Colm) drew inspiration from something found there.


Back in June 2005, "A Little Erdös/Szekeres Magic" took advantage of an observation from the final collection Riddles of the Sphinx and Other Mathematical Puzzle Tales (MAA, 1987). That two-person card effect actually first appeared in "(Smells like)Team spirit" from Mathematical Card Tricks (AMS Online, October 2000).

title                        title

This leaves the comparitively forgotten middle collection Puzzles From Other Worlds: Fantastical Brainteasers from Isaac Asimov's Science Fiction Magazine (Vintage, 1984), issued with two different covers, which includes several topics perfectly suited to card implementations. (What a wonderful MAA reissue this would make!) Below, we merely skim the surface of possibilities suggested by one of its puzzles, in a later iteration in the book.

Considered Yet Given

Consider the magic hexagram below:


(The image here is borrowed from Harvey Heinz's Magic 9x5 Hexagrams.) It appears on page 75 of Puzzles From Other Worlds, and unlike magic squares, is unfamiliar to most audiences. This pattern is doubly magic: each five-number horizontal, vertical, or diagonal row has a sum of 46, whereas each pair of opposite vertices sums to 7.

On page 165, Martin reveals that he was the first to find it, in response to a challenge issued by Harold Reiter in Mathematics Teacher in March 1983. He also found its "complement in 20"—obtained by subtracting each entry from 20—which has magic sum 54. The Heinz link above reveals that more have been discovered since, although far fewer than 57 varieties.

Note that 46 + 7 = 53, which is one more than the number of cards in a full deck. By taking advantage of an idea used in "A Magic Timepiece Influenced By Martin Gardner" (October 2007's Card Colm), we can put all of this to work.

Fan the faces of a jumbled-looking stack of 19 small index cards, on which the numbers 1 to 19 have been written, and deal them out face down on a large table into the above pattern. Turn away and ask for any five-card row or diagonal to be selected, and left in place. Have the remaining cards gathered up and set aside (the technical term for this is "destroying evidence").

Turn back. Quietly note to yourself if the selected row or diagonal includes the central 13 or not. If it doesn't, simply ask that the five index cards be turned over and their numbers added; the total will be 46. Indicate a deck of playing cards sitting on top of a folded page on the corner of the table, and have the person who selected the index cards count down to the 46th playing card. You wrote its value and suit on the page earlier before you folded it, so when the 46th card is arrived at, you can have the paper opened to confirm that it was totally predictable.

If the selected index cards include the central one, you can have even more fun. Pick them up, mix them a little, and hand them out. Ask for the total or the total of the two smallest numbers. (The mixing is to hide the fact that the two smallest numbers are always at each end of the row.) Either 46 or 7 will be reported. If 46, proceed as before, but if 7, hand over the 52-card deck face up and request that the 7th card from the deck face be located, as you mix in the other three index cards in with the rest. The card arrived at is the same as the 46th one from the other end, and hence will match the written prediction.

Here's a less cluttered magic hexagram, which is a type of magic star; it has magic constant 26 for sums of four values in a row.

(The image is from from Wikipedia.) This too can be put to magic use, in a predictable way, one might say. This time, the intial display could consist of any Ace to Queen from a deck, with the forced or predictable card being 26 card from the top of the rest of the deck.

Electric Solvents

The hexagrams above had their summands at vertices. Another type has it summands in its cells. Consider the (unique) magic hexagrams below:


(from Weisstein, Eric W. "Magic Hexagram," MathWorld–A Wolfram Web Resource

Each (multicell) row or diagonal in the hexagram on the left sums to 33, and each corresponding row or diagonal in the hexagram on the right sums to 32. Note that these hexagrams are complementary: given one, the other may be obtained by subtracting its entries from 13. Using an idea implemented in "Sixy Alpha Omegas" (August 2007's Card Colm), we can fudge the 32/33 coincidence to magical effect as follows.

Draw two large blank hexagrams of the type just displayed, in which each cell is large enough to house a playing card. Take out a black-backed deck and show the faces of the cards to demonstrate how "random" they are. Deal out face-down cards from left to right into the rows of one of the hexagram, working from top to bottom, to match the left hexagram depicted above. The deck has of course been set up, only the values (Jack = 11, and Queen = 12) matter, so use a random mix of suits. Next, deal the next dozen cards into the other blank hexagon to match a rotated version of the right hexagram depicted above. Explain that in a moment you will turn away while an audience member picks a row or diagonal from either hexagram of cards. Have a few cards turned over briefly in both hexagrams to "verify" that they are different and unrelated.

Turn away and ask for any five-card row or diagonal to be selected, in either hexagram. Once again, have the rest of the cards gathered up and set aside. Now, have the values of the five chosen cards summed. From a red-backed deck that's been sitting in plain view all along have that number of cards dealt to the table. If 32 cards have been dealt, say, "The next card is yours," whereas if 33 cards have been dealt, say, "The last card is yours." Ask what it is, and have a prediction envelope—also on display from the outset—opened to confirm that you foresaw the outcome, value and suit. All that needs to be done to get this right is to start by jotting down the name of the card originally 33rd from the top.

Celebrations of Mind

John Peterson has written that "when Isaac Asimov was asked whom he thought was the most intelligent person on earth, he answered without hesitation, 'Martin Gardner.'" Centennial celebrations this autumn for this prolific and far-ranging author include numerous special articles and tributes. There's a wealth of Mathematics, Magic, & Mystery to explore at the associated Mathematics Awareness Month site too.

"Trim Hex Anagrams" is an anagram of "Martin's Hexagram." So is "Arrange Maths Mix". (There's another mirthful one we can't print here.) "Considered Yet Given" is one of a huge number of anagrams of "Distroying Evidence," and "Electric Solvents" is an anagram of "Cells Not Vertices."

Monday, June 30, 2014

Dicey Cards

Throughout his long and very productive life, mathematics popularizer Martin Gardner was intrigued by mathematical magic. He wrote extensively about it, and one of his 100+ books served as partial inspiration for the theme of 2014's Mathematics Awareness Month. To mark Martin's centennial year, recent Card Colms (Foregone Outset and Postage Stamp Issue) have drawn on his writings to explore new card diversions, and this month's romp continues that trend.

Entrant Vision

Consider a three-card game where a face-up Ace, 2, and 3 are on offer, and you invite a friend to select any card. If she picks the Ace, you pick the 2 and say, "2 is bigger than 1, so I win." If she picks the 2, you pick the 3 and say, "3 is bigger than 2, so I win," and of course, if she picks the 3, you pick the Ace and say, "Ace beats a 3, so I win." Your friend wouldn't be too impressed, even if you only played one round of this game. If multiple rounds were played, she'd probably complain that you changed the rules as you went along. "The Ace can't be both high and low," she might well cry, "You can't have it both ways." And yet we do have it both ways when playing poker: both Ace, 2, 3, 4, 5, and 10, Jack, Queen, King, Ace are considered to be straights, examples of rare five-card hands.

Wrap-arounds like that of course lead to cyclic arguments; the one above can be summarized as 1 < 2 < 3 < 1 < ... ad infinitum. Cycles are hardly a new concept in mathematics, though there is shock value in seeing them arise in the context of strict inequalities, as we are much more familiar with transitive relations than non-transitive or intransitive ones. Some well-known games exhibit cyclic logic: for instance, rock-paper-scissors. Surprisingly, the three-card swindle above is essentially what's at the heart of much more subtle paradoxes involving dice. We survey some of these before switching our attention to playing cards.

Non-transitive phenomena of this stype first came to the public's attention via Martin Gardner's "Mathematical Games" column in Scientific American, in December 1970. There, he discussed a set of four dice A, B,C, D, discovered by statistician Bradley Efron, for which which A > B > C > D > A ..., in the sense that each die beats the next one listed with probability 2/3. See chapter 22 of Martin's The Colossal Book of Mathematics (Norton, 2001), or Ivars Peterson's "Tricky Dice Revisited."  As Gardner notes there, Karl Fulves published applications of the Efron dice to card effects as early as 1971. Gardner provides several other card incarnations.

Twisted Mortice

We're going to focus on sets of just three dice, for which the margin of victory is generally smaller. There are sets of three non-transitive dice close to ordinary dice for which the margin of victory is very small indeed, but we prefer to focus on those associated with English toy collector Tim Rowett of Grand Illusions. He suggests colored dice on which are the following numbers:

Red = {1, 4, 4, 4, 4, 4},
Green = {2, 2, 2, 5, 5, 5},
Blue = {3, 3, 3, 3, 3, 6}.

Assume the dice are fair, meaning that each of the six sides comes up with the same probability, and consider the game of rolling any two of the dice together, over and over. There are the 6 x 6 = 36 equally likely outcomes. In the case of Red and Green dice, the number on the Red one is less than the number on the Green one 6 + 3 + 3 + 3 + 3 + 3 = 21 times. So 21/36 (or about 58%) of the time, on average, Red loses to Green. Similarly, the Green die loses to the Blue one 6 + 6 + 6 + 3 = 21 out of 36 times, so again about 58% of the time, on average. In conclusion, Green beats Red and Blue beats Green, on average.

The big surprise is that not only does Red beat Blue, on average, violating one's deeply ingrained expectations of transitivity, it does so by an even larger margin. Red in fact beats Blue 5 + 5 + 5 + 5 + 5 = 25 times out out 36, or about or about 69% of the time, on average. Hence we arrive at the circular conclusion:

Red < Green < Blue < Red < ...

Note the similarity to the 1 < 2 < 3 < 1 < ... seen earlier, also bearing in mind the lowest values on each of the three colored dice. Unlike in that case, which required the Ace to be considered low in one context, and high in another, the pairwise comparisons here seem quite legitimate. For the record, all three dice have a mean of 21/6.

The standard way to take advantage these dice is a game where you invite a friend to select any one of the dice, following which you pick another. Decide on a fixed number of throws, such as a dozen, and roll the two selected dice that number of times. If you've picked your die wisely, you should win more often than your friend. Of course, if she picks the Red die, you pick the Green, if she picks the Green you pick the Blue, whereas if she picks the Blue, you pick the Red.

Amusing Strength

For a terrific kicker, play this a few times over, finally revealing your secret technique, then invite your friend to try to beat you. This time, you offer to select your die first, then have her pick one to beat yours. Once it's clear that she has mastered the game, produce a second set of such dice, which she can inspect to verify is identical to the first set. Announce that you'll continue to go first, only this time each of you selects two dice of the same color. The pairs are rolled, over and over, and the totals of the numbers obtained by each of you is used to decide on the winner. The strategy she has just learned will backfire badly on her: If you start by selecting the two Green dice, she will confidently select the two Blue ones, only to find that on average she will lose. Astonishingly, the new cycle of victory reverses the former one:

Red < Green < Blue < Red < ...


Red + Red > Green + Green > Blue + Blue > Red + Red > ...

Secondary Dice (Crayons Decide)

How might all of this work with cards, bearing in mind that a deck only has four cards of each value? The basic idea is to replace each die with a packet of six cards, from which one is randomly selected (with replacement) in between repeated shuffles.

One possibility is to first double each of the values used for the dice, yielding even numbers from 2 to 12 inclusive, then bump a few of them up by 1 to cut down on excessive repetitions. This also neatly sidesteps the issue of whether Aces are low or high.

Red = {2, 8, 8, 8, 9, 9},
Green = {4, 4, 5, 10, 10, Jack},
Blue = {6, 6, 7, 7, 7, Queen}.

Here the colors refer to the card backs for three decks. Red and Blue are standard, find a deck with a different color to represent Green. Suits are irrelevant. (Alternatively, you may opt to do all of this using cards from a single deck, as long as you don't get confused as to which packet is which; perhaps separate the packets on the table with large gaps, and use colored markers or crayons as guides.)

Start with three such face-down packets of six cards, and ask a new friend to pick one of the packets. You pick another one, remembering that Red < Green < Blue < Red < ... as before. The cards in each selected packet are thoroughly mixed and the rolling of dice is replaced by the random selection of one card for each of you from each packet. Record whose card has the highest value, replace the cards in their respective packets and mix them again, and continue. With ten or twelve rounds, you should come out ahead on average, as in the dice case.

Tawdry Codices

Here's another card incarnation with an additional element of randomization, based on some well-known "magic square" dice. Consider the columns of the 3x3 magic square as shown:

2 7 6
9 5 1
4 3 8

Imagine a corresponding packet of face-down cards in mixed suits, running 2, 7, 6, 9, 5, Ace, 4, 3, 8, from the top down. Dealt from left to right, face up, results in this display.

title title title
title title title
title title title

In practice, all dealing is done face down, and the columns overlap a little vertically facilitating order-preserving pickups. Now gather the three columns in any order–maintaining the card order within each column, and deal out again into three piles, from left to right. Repeat over and over, until the cards seem well mixed. Have a friend pick one column (pile) for himself, with or without first looking at the card faces. Turn the other two piles over so they are face up, and casually pick one of them for yourself. If you choose wisely, you will on average win in a game of "best of a dozen" as before, where this time the card packets have size three, simulating 3-sided dice. Once more, your guiding light is 1 < 2 < 3 < 1 < ...: Simply scan the six visible card faces for the Ace, 2, and 3. You will always see exactly two of those. The missing one is in your friend's pile, so pick for yourself the pile that's "bigger and better"—remembering that Aces are both low and high!

Why does this work? Certainly it's easy to check in the case when the three piles are {2, 9, 4}, {7, 5, 3}, {6, 1, 8}, as they are at the outset: then "Pile 2" (the one with the 2) beats "Pile 1" (the once with the Ace) about 56% (=5/9) of the time on average, and "Pile 3" beats "Pile 2" and "Pile 1" beats "Pile 3" by the same margin. This property of the columns of the standard 3x3 magic square (as displayed above) is well known, and is the basis for a set of corresponding non-transitive 6-sided dice where each of the three key values is used twice.

But what about the collection of the three columns in random order, in between repeated dealings from left to right? Since there are six (=3!) ways in which to gather the cards each time, one might expect as many possibilities for the resulting three piles. It turns out that there are in essence only two things that can happen. If the number of rounds of dealing and collecting is even, one ends up with something equivalent to the initial display, from the perspective of competing piles: the order in which the piles occur is irrelevant, as is the internal card order within each pile. For instance, after four or six rounds of dealing and collecting, one could end up with:

title title title
title title title
title title title

While not a conventional magic square, it retains enough magical charm for our purposes: It respects the partitioning of 1–9 into {1, 6, 8}, {2, 4, 9}, {3, 5, 7}, as does the result after any even number of rounds of dealing and collecting.

  On the other hand, after any odd number of rounds of dealing and collecting, we get something like:

title title title
title title title
title title title

This is a representative of a class of equivalent arrays—the partitioning of 1–9 into {1, 4, 9}, {2, 6, 7}, {3, 4, 8}—which are in turn transposes of the kind we saw above after even numbers of rounds of dealing and collecting.

Even better, the 1 < 2 < 3 < 1 < ... mantra again holds here for the new "Pile 1," "Pile 2," and "Pile 3"! That's why the stunt suggested works no matter how many times the piles are dealt out and collected.

Indeed, the two partitions toggled between above are two of five existing for 1–9 that give rise to non-transitive dice, as documented in The On-Line Encyclopedia of Integer Sequences entry Sequence A121228.

There are many more variations on all of the above worth digging out. For instance, M. Oskar van Deventer came up with a set of seven dice such that for any two chosen dice there is a third one that beats them both.

"Recent Divinations" and "Card Intentions Vie" are two of many amusing anagrams of "Non-transitive Dice," and "Entrant Vision" (like "Star Invention") is an anagram of "Non-transitive." "Twisted Mortice" is an anagram of "Tim Rowett's Dice," and "Amusing Strength" is an anagram of "Strange Sum Thing." "Secondary Dice" and "Crayons Decide" are anagrams of "Dicey Cards One," and "Tawdry Codices" is an anagram of "Dicey Cards Two."

Wednesday, April 30, 2014

Foregone Outset

This year's Mathematics Awareness Month theme—Mathematics, Magic and Mystery—is inspired by the extensive written legacy of Martin Gardner, the best friend mathematics ever had, who passed away four years ago at the age of 95.5. Martin was a great believer in the power of curiosity and play in the learning and advancement of mathematics.
             title     title
Among the 30 separate Mathematics Awareness Month webpages of topics and activities on offer for students, teachers, and curious people of all ages—not just in April 2014, but at any time after that—are several that involve cards. These include Bob Hummer parity-based amusements, the ternary arithmetic of the 27 Card Trick, our own additional certainty effect, and the wonderful mathematics of perfect shuffling (and unshuffling).

Coins of the Realm

In due course below, we offer a further card diversion inspired by a Martin Gardner puzzle. In a way, it's a companion piece to our last Card Colm musings on the "Postage Stamp Issue." It's related to a well-known coin problem. Let's start by reviewing "Coins of the Realm"–a problem Martin posed in an old Scientific American column, from June 1964. It's included in Chapter 12 of his Sixth Book of Mathematical Games from Scientific American (W. H. Freeman, 1971), and in the following form in Chapter 1 of his The Colossal Book of Short Puzzles and Problems (Norton, 2006, edited by Dana Richards).
In this country at least eight coins are required to make the sum of 99 cents: a half-dollar, a quarter, two dimes and four pennies. Imagine you are the leader of a small country and you have the task of setting up a system of coinage based on the cent as the smallest unit. Your objective is to issue the smallest number of different coins that will enable any value from 1 to 100 cents (inclusive) to be made with no more than two coins. 
For example, the objective is easily met with 18 coins of the following values: 1, 2, 3, 4, ... 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90. Can you do better? Every value must be obtainable either by one coin or as a sum of two coins. The two coins need not, of course, have different values.
Martin gives two 16-coin solutions, as follows.
1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50
is listed as being given in Roland Sprague's Recreation in Mathematics, and is good for precisely the range 1—100.
1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 47, 48, 49, 51, 52
is listed as having been provided by Peter Wegner, and is good for the larger range 1—104.

Annealing Twofer Whimsy

It's time to re-engage willing participant Willa from the last Card Colm. Take out a deck of cards and shuffle them a little. Deal out sixteen cards in a face-down row, and produce and a piece of paper on which is written a vertical list of the counting numbers from 1 to 20, along with a pen.

Say, "Willa, we're going to play a game. First we'll take turns picking cards from this row until each of us has eight, then we'll try to 'make change' for any amount on this list, using one or two cards from our personal selections. We'll keep track on this piece of paper."

For instance, to make change for 1, each of you needs an Ace, and for 2 either two Aces or a 2. On the paper write Ace next to the 1, and either Ace + Ace or 2 beside the 2. Suits play no role here. You manage to make change for all amounts up to 14, but poor Willa gets stuck long before that. Say something consoling, such as, "I hope you don't think that was a foregone conclusion from the outset."

Say, "Bad luck. Let's try with this other deck. We've exhausted the supply of Aces in that one." Proceed as before, this time letting Willa go first. The results are even better for you, however, as you make it to 15 on the list.

There are three key points here which we haven't mentioned: the cards used are far from random, the shuffling doesn't disturb the top third of the deck, and the "taking turns" picking cards is also rigged in your favor.

title title title title title title title title

As to the cards, the first time around the sixteen cards consist of two Aces, a 3, a 4, two 5s, an 8, and a King, in any order, in the odd-numbered positions considered from left to right. Note that 1, 3, 4, 5, and 8 form the start of the Wegner list above. These cards, shown above, allow for any total from 1 to 14, using one or two at a time.

The cards in the even-numbered positions, shown below, are an Ace, a 2, a 3, and a 5, along with four royal cards. This does not allow for a total of 9 or 10.

title title title title title title title title

Thanks to the "Martin Gardner's Coins to Cards Effect" principle in "Better Poker Hands Guaranteed," you can force Willa to take the cards in the even-numbered positions, leaving the other, winning ones, for you. Here's how: Cards are always picked from one of the two ends of the ever-shrinking row, and you start by picking the card in the first position. Thus Willa's first selection is one of the cards in positions two or sixteen. Next, after pausing as if deliberating carefully, you take the card beside the one she selected, hence one of the cards in positions three or fifteen. Continuing in this way, always taking cards in odd positions, you'll force her to select cards in the even positions, and all will work according to plan. You'll get two Aces (you need two to be able to make change for 2), a 3, a 4, two 5s (both are needed to make change for 10), an 8 and a King; she'll get the others.

The second time around, use the next sixteen cards in the deck, which consist of two Aces, two 3, two 4s, a 9, and a Jack, in any order, in the odd-numbered positions. Note that 1, 3, 4, 9, and 11 form the start of the Sprague list above. These cards, it can be checked, allow for any total from 1 to 15, again using one or two cards. The other eight cards, in the even-numbered positions, are an Ace, two 2s, a 5, along with four cards of value 9 or above. This does not allow for a total of 8. How cruel life can be.

Some entries at The On-Line Encyclopedia of Integer Sequences may be of interest here, such as Sequence A001212.

Opponent Retaliations

There's another way to give the illusion of free choice to Willa while actually being able to guarantee that she'll get the eight cards you want her to. This time, stack the eight cards you want on top of the deck, with the eight she's doomed to get underneath those. Deal sixteen cards to the table, thus putting the cards you want at the bottom. Now, pick up that packet and do the sixteen-card version of what is explained in "Bill Simon's Sixty-Four Principle" for eight cards. The result is that you get the bottom eight cards as desired.

One advantage of this approach is that you can opt to focus on just your winning cards, by only stacking the ones you want on top at the beginning, maintaining them there throughout some fair-seeming shuffling. This means that Willa's cards will be entirely left to chance, and will be unlikely to contain sufficiently many small values for her to even get started on the list. That being the case, you can either start trying to make change at 3 or 4, not 1, or you could reverse the roles and let Willa win each time, by modifying who gets which pile.

"Foregone Outset" is an anagram of "Goes to Fourteen," and "Annealing Twofer Whimsy" is an anagram of "Winning Ways of the Realm." "Opponent Retaliations" is an anagram of "Presentational Option."