The Five-Card Logic Problem

It was one of those lazy days during finals week. One of those days where most people have an exam left, but they just want to forget about it and not study. As I sat on a comfy chair in a lounge on a quiet corner of the University of Washington, my friend Ravi, who had just graduated with a degree in mathematics and economics, lay on the broken, purple couch to my right. My friend Charlotte sat on a purple chair across the table from me. On the table was a deck of cards.

And Ravi posed unto us a logic problem.

The Question

It goes like this: out of a standard deck of 52 playing cards, you draw five cards. You choose one card to keep with you, and you rearrange the other four cards in any order that you please. You then hand the four cards you have rearranged to your partner who has not seen the fifth card.

Can you devise a system that you two can use so that your partner will always know what the card that you are holding is, just by looking at the four cards that you have handed him or her?

Defining the Problem

The first step, of course, was to break down the problem into manageable parts. Any algorithm we could devise would have to do things:

• Identify the suit of the unknown card.
• Identify the number of the unknown card.

And then it was time to get to work.

If you are planning to solve this problem yourself, note that spoilers do follow. All the information you need to solve this problem by yourself is above this point. Anything below this point is part of the solution.

Also, don't get discouraged on this problem too easily. The solution below seems pretty straightforward, but keep in mind that I'm not listing the several possible solutions that failed to work. All in all, this problem took about two to four hours of thinking to solve.

Identifying the Suit

Since there are only four possible suits as opposed to 13 possible numbers or faces, it seemed logical to tackle the suit half of the system first. This part is actually pretty simple.

A standard deck of card has only four suits, so when drawing any five cards you will always have at least two cards with the same suit. This can be used to your advantage very easily. For example, the person drawing the five cards (hereby referred to as the "encoder") can state that the card they will keep with them will always be one of the cards of repeat suit, and that they will place the other card of the same suit on the far left when handing the remaining four cards to the other individual (referred to as the "decoder").

For example, consider the following set of five cards.

2♦
5♣ <-- club
6♥
Q♣ <-- club
6♠

Since there are two clubs present, the encoder would keep one of the clubs and place the other club on the far left in the remaining four cards. For example, if the encoder were to keep the Five of Clubs, the four cards he or she would hand to the decoder would be in this order, from left to right:

Q♣
(other three cards)

Now, with just one card, we are able to identify the suit of the hidden card. In this case, the Queen of Clubs would be referred to as the "suit-indicator card".

Identifying the Number

Before we even start doing anything here, we have to assign each card a number. The numbering system we used was to give the ace a value of 1, to give the cards 2 through 10 their face value, and to give the cards Jack through King the values 11 through 13, respectively.

Currently, we are using one card to encode the suit of the hidden card. This leaves us with three cards to work with for encoding the number of the card. Now, my first step here was to calculate the maximum information content of three cards using just permutations. With three cards there are six possible permutations. That's six possible numbers you can represent by rearranging the three cards. To do this, you can number the three cards from lowest to highest. Say that the lowest card is 1, the middle card is 2, and the highest card is 3. You will also need an order of the suits so that if you have two cards of the same number you can tell which card is higher. Then you get the following possibilities by rearranging the three cards in different possible orders:

#1: 1, 2, 3
#2: 1, 3, 2
#3: 2, 1, 3
#4: 2, 3, 1
#5: 3, 1, 2
#6: 3, 2, 1

Now, it doesn't take a genius to figure out that expressing thirteen different values is a bit difficult with six numbers.

But what if we use the suit-indicator card as a base? Think about it: in our previous example, the suit-indicator card was Q♣. Now we can encode a number from one to six to add on to five. For example, if we arrange the cards in permutation #1 from above, that would be considered encoding the number one. So we would add one to our suit-indicator card, and get Q♣ + 1 = K♣. Thus, the hidden card would be the King of Clubs.

Of course, in our case, the hidden card is not the King of Clubs. It is the Five of Clubs. Now, the question is, how do you add any number between one and six to twelve (the Queen) and get five? The answer is modular arithmetic, my friend.

Think about a clock. What time is it three hours after 11 AM? Why, 2 PM of course. You are adding a number (3) to a larger number (11 AM) and ending up with a smaller number (2 PM). The key here is to think of all 13 possible card values has numbers on a clock with 13 hours on it. The Ace would be the 1 and King would be the 13 on this clock. So, for example, adding 2 to 13 (the King) would get you 2.

Basically, you add your number on to the suit-indicator card's number, and if the value is higher than 13, you subtract 13. Using this logic, you can add six to the Queen and get five. What you are doing is 12 (the Queen) + 6 = 18. Since 18 is higher than 13, you subtract 13, and 18 - 13 = 5. So for our example problem above, we would encode the sixth possible permutation. To do this, we'd first order our three non-suit-indicator cards from lowest to highest and then assign them numbers from one to three. We are using the suit order clubs, spades, diamonds, hearts for when cards have the same number:

#1: 2♦
#2: 6♠
#3: 6♥

Now we look back out our table of permutations and find that the sixth permutation is "3, 2, 1", so we arrange our three cards as such:

6♥ 6♠ 2♦

Then we add our suit-indicator card (Queen of Clubs) on to the very left, as we agreed to in the previous step, giving us the final card order:

Q♣ 6♥ 6♠ 2♦

Decoding Cards

For a lot of people, this system only makes sense when they see the decoding step. Let's start with the four cards from above:

Q♣ 6♥ 6♠ 2♦

Now, we have agreed with the encoder that the card on the far left will always be of the same suit as the card that the encoder keeps. Because of this, we know that the hidden card must be a club right from the start. Now, let's eliminate the far left card for the moment and consider the three other cards:

6♥ 6♠ 2♦

If we assign these cards numbers such that 1 is the lowest card, 2 is the middle card, and 3 is the highest card, we get:

3 2 1

From our table of permutations above, "3, 2, 1" is the sixth permutation. Therefore the number that is encoded is 6. We have to add this number to the card that was originally on the far left, the Queen of Clubs. A Queen corresponds to the number 12, so we add 6 to 12 and get 18. Of course, 18 isn't a real card, so we have to subtract 13, and get 5. We can conclude that the hidden card is the Five of Clubs, which is correct.

The method employed here is pretty easy to get a hang of and to memorize. Even the table of permutations can be easily memorized since it is in numerical order. If you and a friend can indeed memorize this system, you've got an awesome trick to show off at parties.

This writeup suggests a possibly superior solution to the previously suggested logic problem of being handed five cards at random from a deck of cards, being allowed to choose one and hand the remaining four cards to another participant in any order you choose, with the goal that you can communicate to that other person what card you have.

Rather than going through a huge, circuitous method, actually, there's another, far simpler solution which you could use, and is also a lot more extensible (eg it can handle extra cards, such as jokers or that "rules for poker" card you get with some decks). The key is to simply realise what information you want to transmit, and what "signals" you have. While both this solution and the one previously put forward by rdude work, this solution offers a more "general" solution to the problem, removing any reliance on the presence of suits or any other feature of a normal deck of cards, and also being able to handle additional cards in the deck, such as jokers.

Overview

The information you want to transmit is what card you have. Suit/Value is part of it, but that's not really relevant to consider on its own. What you need to get to the other person is which of 52 cards you have (actually 48 if you consider the other person knows you don't have any of the four they're holding). This can most simply be done by "transmitting" a number between 1 and 52, which can quite trivially be reverted back to the card you're holding (1-13 for hearts, 14-26 for diamonds etc). If you think about it, this can be communicated using 6 bits of information, since 6 bits can communicate 64 different values.

Now, where can we get those 6 bits of data to the other person? Well, there's a lot of ways, because we have so many ways to communicate data here, but here's one example.

Card Order

Firstly, there are 4! (equal to 4x3x2x1, or 24) different ways to order the cards you give to the second participant. The simplest way for this to be applied is to treat each of the cards as if they were numbered between 1 and 4, based on their numerical value between 1 and 52 (using the same system as before, 1-13 for hearts, etc). While you could use all 24 permutations to carry data, for the sake of simplicity, it's enough to define 16 permutations. So, based on the permutation the second participant is handed, they can determine the number between 0 and 15, and convert that into a binary number between 0000 and 1111.

Handing Over Cards

Now, that's enough to get 4 bits of data across, what about the other 2? This can easily be done by the way in which you hand the cards over. To carry two bits of data (or four permutations), you can do this by how many cards you hand over at a time. For example:
Binary 00: Hand over all four cards in one go
Binary 01: Hand over the first two cards, then the remaining two cards
Binary 10: Hand over the first card, then the remaining three
Binary 11: Hand over the first three cards, then the remaining one

So you see, no variation to the order of the cards has been made above, so the 4 bits of data being transmitted by the card order is intact.

Finding the Solution

To find out what card is being held, take the 4 bits from the order of the cards, and combine it with the 2 bits from the way they're handed over, for a total of 6 bits, which can be converted into a number between 0-63 (though only numbers between 1 and 52 will be used), which will be the number of the card being held. If necessary, jokers can be found using the above method by being given numbers such as 53 or 54.

Example

I recognise the above explanation isn't the simplest, so here's an example of how it can work:
You are handed five cards, you select one of them as you like, let's say it's the two of hearts, numbered "2" in our card numbering system. This can be converted into binary, which will be 000010 (binary 2).

You then take the remaining four cards, and calculate their numbers in the numbering scheme. Let's say hypothetically they're 10,20,30 and 40 to make things simple. Since you want to communicate 0000, you'd arrange the cards in whatever order you had preplanned to signify that (presumably 1-2-3-4), so you'd have the card "numbered" 10 first, then 20, then 30, then 40.

You then have to communicate the binary digits 10, so using the scheme shown previously, you would hand the second participant the card "numbered" 10 first. Then, you would hand them the cards "numbered" 20, 30 and 40 in the one bunch, in that order. From this the second participant will know the last two binary digits are 10.

In order to get the first four digits, your partner will examine the order of the cards they have received, and on realising they are in the order signifying 0000, will realise the whole binary number you are communicating is 000010, which is the number for the two of hearts.

So sure, you could combine all sorts of things to find the solution as in rdude's suggestion, or you could use this system, where you don't have to choose any specific card out of the five you are given, and more importantly can handle jokers or other cards.

Update

I've just had an extremely clever suggestion (which was actually a criticism of how "easy" my suggestion can make things) from Waldemarexkul where it is in fact possible to communicate all six bits of required data solely in the "handing over the cards" stage, so that it would be possible to determine the card being retained without even having to look at the values of the cards being handed over. In addition to the two bits which can be obtained by the timing of handing over the cards, an additional four bits can be transmitted by handing over each card either face up or face down, with each card's "face up" status constituting one bit in the final calculation. Heck, with all these different ways to communicate the data required, it'd be possible to achieve this task using only four cards. So perhaps this shouldn't be the five-card logic problem, but the four-card logic problem?