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."

Friday, February 28, 2014

Postage Stamp Issue

There's no denying that the theme and spirit of Mathematics Awareness Month 2014 is inspired by the landmark book Mathematics, Magic and Mystery (Dover, 1956) by legendary writer Martin Gardner, the best friend mathematics ever had.

title      title 

The beautiful MAM 2014 poster on the right here, a high resolution version of which can be downloaded, was designed by Bruce and Eve Torrence of Randolph-Macon College. It echos many of Martin Gardner's most beloved motifs: magic squares, knots, geometric vanishes, Möbius bands, illusions, and playing cards.

The Alumni Midterms

Did somebody mention cards? For us, Martin's extensive legacy has proved to be a rich source of ideas for amusements with cards, going back to 1999, and many of these have surfaced in Card Colms. It seems appropriate, in his centennial year, to focus on new card activities derived from things Martin wrote about. What follows may serve as a way to generate interest in a classic combinatorial problem.

Find a willing participant; let's call her Willa. A red-backed deck and a blue-backed deck are produced, and you quickly run through the cards in each deck face up, tossing aside all Jacks, Queens, and Kings. "We won't need those," you say, before giving Willa free choice of the two slimmed-down decks. Assume she takes the red deck and you take the blue one.

Say, "Willa, let's play a game. We'll first do it with your deck, then we'll try it with mine. First you need to shuffle the cards. Please split the red deck roughly in the middle, and riffle the two resulting halves together." While Willa is shuffling, produce a pen, and a piece of paper on which is written a vertical list of the counting numbers from 1 to 30.

Continue, "Please lift off the top half of those shuffled cards, as best you can estimate, it doesn't have to be precise. I get the other half." Set aside your half for later. "Now, please take about half of your cards, that should be ten cards, roughly. Your goal it to see how high you can get on this list, using at most three of these random card values added up, I'll keep track for you. Please look at your card faces, do you have an Ace? Great!" She does, and you write write A next to the the 1 on the list. Next to the 2 write either 2 or A + A, depending on whether she has a 2 or two Aces. Keep going as long as is possible, beside each number writing the values of cards she has which equal or add up to that number.

The first time three card values are used, pause, and say, "Sorry, I forgot to mention that to make it more interesting, whenever you have three card values making up a particular number, you must use one of those cards again for the next number. Got it?" Since, you only just sprung this surprise on Willa, offer her the chance to redo that first three-value sum if she wants to.

The result of Willa's efforts might be all numbers from 1 to 16 (or some other number) achieved, before she failed to get 17 subject to the "continuity" condition when using three cards. Have Willa do it all over, with the other roughly ten cards of her half deck, and another copy of the list. The results should be along the same lines.

Yet, when you do the same with your cards, in two approximately 10-card palettes just like Willa, with her keeping track this time, on new copies of the list, you should do much better, getting to 25 or maybe even higher.

The deck is rigged of course. Suits are irrelevant. You want to end up with three 4s and 5s in in your initial twenty cards, with Willa only getting one each of those values in hers. Furthermore, you arrange it to that each of you starts with an Ace and a 2 in each of your 10-card card palettes, otherwise it's hard to get started! It turns out that having several 4s and 5s helps you to beat her.

Here's a suggested set-up, consisting of four 10-card packets.

Packet A is these cards in this order, from the top down: any Ace, 2, 5, 7, 8, 4, 2, Ace, 7, 8.

Willa will end up with most of these, and the first and internal Ace and 2 for sure. You're letting her have one 4 and one 5 to deflect suspicion, otherwise, she may notice upon repetition that she never had a 4 or a 5. It turns out that if you had all four of each (and even more Aces) you'd be sure of getting to at least 15.

Packet B is these cards in some jumbled order: all of the 3s and 6s, and two of the 7s.

You will end up with most of these.

Packet C is these cards in some jumbled order: all of the 9s and 10s, and two of the 8s.

Willa will end up with most of these.

Packet D is these cards in this order, from the top down: any 4, 5, Ace, 2, 5, 5, 4, 4, 2, Ace.

Most importantly, you will end up with most of these, and the internal and last Ace and 2 for sure.

Stack A on top of B, on top of C stacked on top of D. Randomly insert the Jacks, Queens and Kings; they're only to add to the illusion of fairness, as they are pulled out again at the start of the effect. When Willa splits the resulting 40-card deck, she more or less riffle shuffles A and B into C and D.

Furthermore, when she takes the top half of that for herself, she should get most of A and C, in such a way that the final split into two roughly 10-card packets gives her an Ace and 2 in each. Similar conclusions apply to the cards you end up with, which are more or less B and D.

The restriction about having to reuse one of three cards used for a previous sum is designed to make it harder for Willa to win.

It can be repeated with the other deck, which we suggest arranging in an order which exactly mirrors the type of set-up just proposed, i.e., runs in the opposite order. That way, you can take a gamble on saying, "Let's try that again. Maybe you'll have more luck if you take the bottom half of the deck this time." You may want to vary the card set-up a little so Willa doesn't realize that she's been duped a second time.

We now explain the mathematics underlying this game.

Aha! Little Poet

title      title

This month's Card Colm was inspired by Martin's science fiction puzzle tale "The Postage Stamps of Philo Tate" on page 15 of Mathematical Puzzle Tales (MAA, 2000), which is a reissue of Science-Fiction Puzzle Tales (Potter, 1981). That tale concerns the classic postage stamp problem (see Wikipedia and MathWorld).

Postage stamps in D different demoninations (or values) are available. What amounts of postage can be made up using at most S stamps, where stamps of any denomination (or value) may be repeated?

For instance, if D = 2, the values being 1 and 2, and S = 2, clearly we can make up 1, 2 (in two ways, as 2 or 1 + 1), 3 = 1 + 2 and 4 = 2 + 2, and no other amounts are possible. On the other hand, if D = 2 and the values are 1 and 3, and S = 2 again, then we can make up 1, 2 = 1 + 1, 3, 4 = 1 + 3, and 6 = 3 + 3, and no more amounts are possible. Note that 5 is not possible.

The goal is to be able to make as a large an unbroken range 1 to R as possible using the available stamps, subject to a restriction on how many stamps can be used. In both examples above—where we can use up to two stamps of two values—it's 1 to 4. However, if D = 2, the values being 1 and 5, and S = 2, then 3 is not possible, so R = 2 this time. Obviously, we must always include 1 in the values allowed to even get started.

If D = 3, the values being 1, 2 and 5, and S = 2, then it can be checked that 1 to 7 are possible, as is 10, but not 8 or 9. Here R = 7.

If D = 3 again, with values 1, 2 and 5, but S = 3, then it can be checked that 1 to 12 are possible, but not 13 or 14, though 15 is. Here R = 12.

The following table lists some of the optimal results when S = 3, i.e., when we use up to 3 stamps of various values, for various numbers D of denominations or values. Additional information can be found in Sequence A001213 in The On-Line Encyclopedia of Integer Sequences. One entry in the table is intentionaly left blank; filling it in correctly leads to a pleasant surprise or two.

Using up to 3 stamps
D = # of values values range 1 to R
2 1, 3 1 to 7
3 1, 4, 5 1 to 15
41, 4, 7, 81 to 24
51, 4, 6, 14, 151 to 36
6?1 to 52

If we consider specific small values of D, for any S, then the maximal R are given by the following entries at The On-Line Encyclopedia of Integer Sequences,

D = 2 values, S = n stamps: Sequence A014616

D = 3 values, S = n stamps: Sequence A001208

D = 4 values, S = n stamps: Sequence A001209

D = 5 values, S = n stamps: Sequence A001210

D = 6 values, S = n stamps: Sequence A001211

Likewise, if we consider specific small values of S, for any D, then the maximal R are given by these entries at The On-Line Encyclopedia of Integer Sequences

D = n values, S = 2 stamps: Sequence A001212

D = n values, S = 3 stamps: Sequence A001213

D = n values, S = 4 stamps: Sequence A001214

D = n values, S = 5 stamps: Sequence A001215

D = n values, S = 6 stamps: Sequence A001216

Information about arbitrary values of D and S is coded in this sequence: 

D = k values, S = n stamps: Sequence A084193

Readers still in search of a little thrill may enjoy recent reflections on some old magic and the recycling of the principle from the first Card Colm over at the Huffington Post's "Magical History Tour." 

"The Alumni Midterms" is an anagram of "Three Summand Limit" (so is "The Untrimmed Mails"), and "Aha! Little Poet" is an anagram of "Philo Tate Tale!"