Sunday, July 20, 2014

Solution to the card-deck challenge

Hello again for part 2 of my guest appearance.

You guys are fantastic! Cory and I were very impressed by your suggestions and creativity at solving the card-deck challenge:

Five random cards are drawn from a deck of 52 cards (four suits and 13 cards per suit). You see all five cards and can decide which four of those cards you want to reveal to your partner, and in which order. Is there an ordering scheme that you and your partner can agree on beforehand that allows your partner to determine the fifth (hidden) card from the choice and order of the four cards that you reveal?

The three correct solutions that we received were from Douglas, James, and Vince. Congratulations to all three of you!

If you want to solve it yourself, this is your last chance. I will reveal the solution below this cute lolcat:



Okay, here we go. Surprisingly, such a scheme can be found, and it's actually easy enough to memorize so that you can perform this at your next dinner party. Below I explain one possible scheme, and there are certainly many other conventions that would work just as well.

As a reminder, all we have to choose is which card we hide and want our partner to guess, let's call this card the target, and in what order we want to reveal the other four cards.


We need to signal the suit and the value of the target card. The former is easy: Since we are given five cards of a deck of four suits, we can employ one of my favourite "you don't say" math theorems, the Pigeonhole principle, to realize that there will always be a pair of cards with the same suit. Hence:


Rule 1: The first card that you reveal is the same suit as the target (the card that will be hidden).

So far so good, by revealing one card we reduce the number of possible targets from 48 (52 - 4 revealed cards) to 12 (13 - 1 revealed card of the same suit).

To signal the rank is harder, because in the worst case we don't have any influence about which three cards Rule 1 leaves us with. So we have to assume these three cards are entirely random. All right, how many ways do we have to order three random cards? That's 6, because there are three choices for which card to show first, each of those gives us two choices of which card to show second, and the last card is determined by that: 3*2 = 6. This means that we can signal any number 1, 2, 3, 4, 5, or 6. A simple scheme of how to signal which number exactly is below, all we need to know at this point is that six different patterns is all the three middle cards can give us.


Rule 2: Use the three middle cards to signal the distance in rank between the first card and the target.

That's almost the entire trick, but there is one more idea required to reduce the number of possible targets from 12 to 6. To begin with, we realize that Rule 1 just says that one of the two cards of the same suit needs to be revealed first, but it does not state which one. For example, we could agree to always show the lower of the two cards, and then using the three middle cards to signal how many ranks higher the target is. This works well in half of the cases: Whenever the higher card is at most six ranks higher than the lower card. For example, given these five cards

Following Rule 1, we have to choose one of the clubs as the target. Choosing ♣K as target we can use the non-clubs to signal that the target is five ranks above the ♣8, which is possible by Rule 2.

we would choose the target to be ♣K, the first card to be ♣8, and the three remaining cards to signal a five, since the King is five ranks higher than the Eight.

And what do we do when the two cards of the same suit are more than six apart? The beautiful answer is: They are not! At least not modulo 13:

No two cards can be more than six ranks apart (modulo 13).

It turns out that the distance between any two of the 13 cards of the same suit is at most 6 (=floor(13/2)), if you continue counting from the beginning once you hit the Ace. For example, the distance between Q and 3 is four, the distance between J and 4 is six.


Rule 3: Choose which of the two possible first cards to show (Rule 1) such that the targets' rank is at most 6 (modulo 13) ranks above the first card.

And that's all there is to it. We are now able to choose four cards in such a way that our partner will be able to calculate the remaining fifth card. For example:

Given ♣2, ♣A, ♠Q, ♡3, ♡Q, we can either play for clubs and show ♣A first and signal one, or play for hearts, show ♡Q first and signal four.

We can choose if we want to let ♣2 or ♡3 be the target.

As a final step, here is a scheme of how use the three middle cards to signal the number 1, 2, 3, 4, 5 or 6: Start with choosing an order for all 52 cards. For example: The higher the rank, the higher the card, and if the rank is the same, then use the suit order ♣ > ♠ > ♡ > ♢. Once we agree on the order of the three cards, low, mid, high, it is easy to translate that into the numbers from 1 to 6:

low, mid, high -> 1
low, high, mid -> 2
mid, low, high -> 3
mid, high, low -> 4
high, low, mid -> 5
high, mid, low -> 6


Concluding examples

1) Given these five cards, ♣8, ♣K, ♠Q, ♡6, ♢Q, which cards should we reveal and in which order?

According to Rule 1, the first and target card will be a club. The ♣K is 5 ranks higher than the ♣8, while the ♣8 is 8 ranks higher than the ♣K. Hence, according to Rule 3, we first reveal ♣8 and let ♣K be the target. With the remaining cards ♠Q, ♡6, ♢Q we have to signal 5, and hence reveal the highest card second, ♠Q, then the lowest, ♡6, and as fourth card the middle, ♢Q.

2) Given the cards in the initial screenshot, the target card must be ♢A, because that's the spade which is one (the three middle cards are sorted in low, mid, high) above the ♢K.


The hidden target card is ♢A, because that's the spade one rank higher than the first card ♢K.

Addendum:

A similar, yet distinct, solution is the following: Ignoring Rule 1 and the suits gives us 4*3*2 = 24 ways to reveal four well-ordered cards. We reveal 4 of the 52 cards, leaving us with 48 possible targets. Since two cards can be at most 48/2 = 24 ranks apart (use a larger version of the circle and calculate modulo 48) we can agree that the target card is 1, 2, ..., or 24 ranks higher than the highest revealed card.