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.