Monday, April 30, 2012

Splitting the Pot

Dedicated to the memory of Thomas M. Rodgers (1944-2012)

In the February 2012 Card ColmAmazon Arrays (Large Action), we considered 4 by 4 arrays such as,
Each row (and each column) contains each suit once, and each row (and each column) contains each of the four values Jack, Queen, King & Ace once. Hence we have an example of an orthogonal (or Graeco) Latin square, which can be dealt from a packet of sixteen cards in four columns and rows from left to right.

Gather these cards together, shuffle, and again deal face-up left to right into four rows and columns. (Overlap a bit vertically, to facilitate later top-to-bottom gathering by columns.) It's likely to end up with an array such as the following, devoid of the special characteristics of the last one.

Yet, some structure remains. Can you see what it is?

No matter how the cards are dealt, it's possible to pick out one from the first column,
another from the second, a third from the next one and a final one from the fourth,
so that overall we have selected one Jack, Queen, King and Ace, in some order.

The same now holds for the remaining columns of three cards on the table, and the columns of two cards that result when those four cards are removed, and so on until we have just one card of each value remaining, in a single left-to-right row. It's instructive to confirm these claims, one by one, for the array above. To understand why it's all true, perhaps work up from 2 by 4 arrays of two Jacks, Queens, Kings and Aces, to 4 by 4 arrays of four of each.

The highlighted claim above is equivalent to saying that it's possible to reorder the cards within each column, so that each resulting row contains one card of each value.

We are not claiming that the first Jack in the last row above can be replaced by a King above it; that would be too much to ask for. However, the second Jack in the last row can be replaced by the King three cards above it, so all is well.

The highlighted claim above is equivalent to saying that it's possible to reorder the cards within each column, so that each resulting row contains one card of each value. Here is the result of four column reorderingsamong several possible ones for each column-for the last 4 by 4 array. It utilizes the switch just suggested:
Of course everything just claimed about random arrangements of these sixteen cards holds true if the words "row" and "column" are interchanged throughout, or if we focus of the four suits rather than the four card values in question.

However, as we move forward, we concentrate on the occurrences of distinct card values from left to right, across columns, there being corresponding observations for suits from top to bottom, across rows.

Is this all a special property of square arrays? To find out, let's pick up the cards, throw in the four 10s too, shuffle the resulting packet of size twenty, and deal out left to right into five face-up columns of four cards. Something like this will be seen:
Once again, some structure is evident. As above, it's possible to pick out one card from each row, to that overall we have one of each suit. Also, extending what we had above,

No matter how the cards are dealt, it's possible to pick out one from each column ,
so that overall we have selected one 10, Jack, Queen, King and Ace, in some order.

The same now holds for the remaining columns of three cards on the table, and the columns of two cards that result when those four cards are removed, and so on. It's worth confirming these claims for the array above.

Of course, it's all equivalent to saying that it's possible to reorder the cards within each column, so that each resulting row contains one card of each value. Can you perform five such column reorderings for the last 5 by 4 array?

Let's not stop there. Shuffle the entire deck, and deal into thirteen columns of four cards. It should not come as a surprise that no matter how the cards are dealt, it's possible to pick out one from each column so that overall we have selected one 2, 3, 4, ..., 10, Jack, Queen, King and Ace, in some order. It's also possible to pick one card from each row to end up with one of each suit. Similar observations apply to the scaled-down arrays resulting as the desired sets of card are removed.

So, what's going on? Colin Wright kindly alerted us to a tie in with Philip Hall's Marriage Theorem. David Leep & Gerry Myerson consider this application in their 1999 American Mathematical Monthly paper Marriage, Magic & Solitaire. Most of the proof can also be found online on page 7 of Notes on Matching by Jonathan Hirata.

Can you find a more elementary (or direct) proof in the case of n by m arrays of cards as considered above?

Deal/Ply/Finagle, Live

Ask for four poker players to step forward. Hand the 10s, Jacks, Queens, Kings and Aces to the first of them, and have that packet of cards shuffled and dealt into five overlapping face-up columns of four cards each. Comment briefly on the arrangement that results, and quickly pick up the columns one by one, gathering from top to bottom, shuffling each in hand before dropping it in a face-down pile. Gather the piles in any order, perhaps asking others for input along the way.

Hand the packet back to the first player and have it dealt again, but this time into four overlapping face-down columns of five cards each. Pick up one of the columns and hand it to the player, saying, "These cards are destined for you. Please don't look at them yet."

Gather up the remaining fifteen cards and hand them to the second player to shuffle and deal into five overlapping face-up columns of three cards each. Again comment on the arrangement that results, and quickly pick up the columns one by one, gathering from top to bottom, shuffling each in hand before dropping it in a face-down pile. Gather the piles as before.

Hand the packet back to the second player to deal into three overlapping face-down columns of five cards each. Pick up one of the columns and hand it to the second player, saying, "These cards are destined for you. We'll look at them later."

Gather up the remaining ten cards and hand them to the third player to shuffle and deal into five overlapping face-up columns of two cards each. Quickly pick up the columns one by one, gathering from top to bottom, shuffling each in hand before dropping it in a face-down pile. Gather the piles as before.

Hand the packet to the fourth player, saying "Let's get you involved too," and have it dealt into two overlapping face-down columns of five cards each. Say, "There are two poker hands here, you get to pick which one you want." The other one is then given to the third poker player.

Stress the randomness of all than has taken place, the repeated shuffling, the fact that the cards were out of your hands, and so on. The last point is not entirely true of course, but you can point out that you shuffled the piles as you gathered them, and others decided in what order they were collected.

Have the four poker players inspect their cards. They should all have straights: a 10, Jack, Queen, King and Ace, with the suits jumbled randomly. End with some congratulations, and "I guess you'd split the pot if this was a real game."

Should one or more person happen to have straights in just one suit, this is extra reason for celebration; act like it was entirely expected.

How can such order be wrestled from chaos? There are two secrets here: your knowledge of the principle discussed earlier, and some hitherto unmentioned details as to exactly how you shuffle those columns as you gather them up!

Let's suppose that the initial display of cards is the one seen earlier above:

Quickly scan horizontally, seeking a complete row, namely one of each of the five values, or a relatively complete row, such as the third row above, or maybe just focus on the last row, which has three Queens here. There are three possibilities to consider.

If a complete row is spotted, say the second one, then gather up the columns in any order, and after the cards are dealt again, face down, have the second column of five cards given to the first player as a poker hand.

If a relatively complete row such as the third one above catched your attention, then conspire to have the Queen at the bottom of the third column there switched with the King above it as the columns are gathered up; which results in the third column of five cards dealt being a suitable poker hand for the first player.

Perhaps a more convincing approach, however, is to focus on the final row: if the Queens at the bottom of the second and third rows could respectively be switched for either of the 10s or Kings above them all would be well, allowing for gathering in any order and dealing and finally setting aside the last resulting column of five cards as the poker hand for the first player. The same effect can be achieved as follows: gather up the first column and do some casual in-hand shuffling of these four cards, discretely peeking at the bottom and only stopping when the Ace is back there. Place the cards face down in a pile on the table, and repeat for the second column, this time shuffling until either of the two 10s are spotted at the bottom. For the third column it's a King that needs to end up on the bottom. For the last two columns, either the card already at the bottom, or a card of the same value, needs to end up there. In any event, it's the final column of five cards dealt that forms a suitable poker hand.

Of course the poker players don't know where this is going, and hence don't know what to look out for, so you can probably get away with it. The same strategy is applied in later rounds. The frequent shuffling by the players, and the random order in which the piles are collected by you, seems to add to the fairness, but neither has the slightest impact on the outcome.

Curiously, "A Gatherer Memoir" is an anagram of "Marriage Theorem." Two decades ago, Thomas M. Rodgers was the original gatherer for Gardner; of fans of mathematics, magic, puzzles and more. The Gathering for Gardner conferences he helped to start have grown into tremendously stimulating, innovative, and wide-ranging affairs, bringing together creative like-minded souls in the arts, mathematics and related fields.

The Gathering for Gardner offshoot concept, Celebration of Mind, another product of Tom's vision and energy, with even more potential to make an impact far into the future, takes place worldwide every October. These events are free and open to all. Please participate by either attending or hosting one yourself!

Thanks to Colin Wright for the initial inspiration this month.

"Deal/Ply/Finagle, Live" is an anagram of "A Level Playing Field."