First, here is the original question which was also discussed here in Puzzling Beta:
This is a two-person card trick. At the initial stage, the magician leaves the room. The magician's assistant takes a pack of playing cards (fifty-two cards, no joker), gives it to the audience, and they choose five cards in whichever way they prefer. Then, the assistant inspects the five-card collection, chooses one card from that five-card collection and gives it back to the audience. After that, the assistant arranges the remaining four cards in some order and puts the pile on the table, all face down. Finally, the magician comes in, inspects the pile, and announces the fifth card. (Example game: The pile consists of, in order, the seven of spades, the queen of hearts, the three of diamonds, and the eight of clubs. And the magician announces “You have the king of spades.”) Assuming no illicit information is passed, how can this trick be done?
Question: The jolly joker is added to the pack (so it contains fifty-three cards). Devise a method to perform the same trick.
Answer
Say you take any five cards from a deck. Since there are only 4 suits, there must be at least two of them which have the same suit. One of these will be our chosen card that we will get the magician to guess.
If you pretend the cards are the numbers on a clock (with an extra number since there are 13 values), then the most these two numbers can be apart could every be apart clockwise is 6 spaces. If you go 7 spaces away clockwise from any number, then continuing clockwise 6 more spaces will get you back to the original!
So, take the "larger" of the two (i.e. the one that is 6 or less spaces ahead of the other going clockwise). This will be the chosen card that you give back to the audience which you will get the magician to "guess".
Put the other card of the same suit (the "lower" of the two) as the first card in the pile that we will show to the magician.
Now, the final three cards can be ordered in $3!=6$ different ways to tell the magician the offset of the second card from the first. Using alphabetical order of the suits to break ties, we can order these cards in one of 6 possible orderings. Here is are the six orderings:
$$O(1)=\{c_1, c_2, c_3\} \implies +1$$ $$O(2)=\{c_1, c_3, c_2\} \implies +2$$ $$O(3)=\{c_2, c_1, c_3\} \implies +3$$ $$O(4)=\{c_2, c_3, c_1\} \implies +4$$ $$O(5)=\{c_3, c_1, c_2\} \implies +5$$ $$O(6)=\{c_3, c_2, c_1\} \implies +6$$
Example 1
For example, say the 5 cards are the 2 of clubs, 10 of clubs, 8 of diamonds, 9 of hearts, and Jack of spades.
We can see that there are two cards which are clubs, and the 2 is 5 spaces away counting up from the 10 (wrapping around when we hit the Ace). Thus, pick 2 as the hidden card, and put the 10 as the first card. Use the $O(5)$ of the other three cards.
10 of clubs, J of spades, 8 of diamonds, 9 of hearts
The magician would recognize $O(5)$ among the last 3 cards, and then count up 5 from the first card, wrapping around when necessary. He would then correctly guess the 2 of clubs.
NOTE: I've had to revise this answer extensively since the OP rudely kept finding holes in the solution. I now have what I believe to be fool-proof method. But I could be wrong, so please try to find counter-examples! (but not too hard...)
NOTE 2: I created this proof based on Appendix A of http://www.nymphomath.ch/crypto/magie/cardTrick.pdf. The solution presented there does not work (I have mailed the author and am awaiting reply), but I was able to infer a correct solution from that and present it here.
NOTE 3: If you read the paper above, you will find reference to the original author of the solution. There is an email in which it is presented here https://github.com/cstrahan/aduni/blob/master/02_discrete_math/misc/Card%20trick/Weiping-53.txt. It turns out my solution is pretty much this one exactly, just longer and less elegant.
Strategy
First, we will add the joker as the 14th spade between the King and Ace. (Note, this solution looks like it can easily expand to a 56 card solution by adding a joker to each suit. However, if you have 2 suits represented in the 5 cards, each pair 7 apart, it is not obvious how to reconcile this.)
For most cases, the solution without the joker works fine. The only time it doesn't is when you have 2 spades which are 7 apart from each-other, and the other 3 cards are from the other three suits.
So, here are the scenarios in order of preference.
Any 2 cards of the same suit, non-spades
Simply use the non-joker solution. Even if there is a pair of spades, use the non-spade pair.
3 or more spades
This scenario must be treated somewhat specially in order to not confuse it with the scenario below. Basically, you will use the non-joker solution, but since there are multiple spades, there is more than one possibility for the hidden card. When presented with this scenario, we must simply choose the two spades such that when we encode, we do not leave exactly 2 spades showing which are exactly 7 apart. Since we have 3 distinct numbers, this will always be possible.
Only 2 spades, not 7 apart
Again, use the non-joker solution.
Only 2 spades, 7 apart
In this case, we have all the suits represented, otherwise we would have been able to use the non-joker solution with a different suit. So we will hide one of the non-spade cards and put one of the spades as the first card. Since we will end up showing both spades, one of them being the first card, the Magician will be able to recognize this scenario. He will see the first card is a spade, and there is a second spade showing 7 from it. He will know that we hid a card of the missing suit.
Now, of the 3 non-spades, we need to decide which to hide. Notice that you will always have one of the following:
- All three non-spade cards are in $[A-7]$
- 2 non-spade cards are in $[A-7]$, 1 is in $[8-King]$
- 1 non-spade card is in $[A-7]$, 2 are in $[8-King]$
- All three non-spade cards are in $[8-King]$
Thus, at least two of these cards share the same interval. If all three do, then ignore the lowest and use the two highest. We will hide one of these two cards. Also, we will use the spade in the first position to indicate which interval the hidden card is in. The lower of the two spades in the first position indicates it is in the $[A-7]$ interval, and the higher of the two spades indicates it is in the $[8-King]$ interval.
Now, of the two cards in the same interval, we can use the same trick as in the non-joker solution to get the value of one from the other. Before, we had 13 numbers on the clock, so were able to use offsets of up to 6 clockwise from one to get to the other. Now, we have only 7 numbers on the clock, so all we need is up to 3 clockwise from the other. This is easy to encode with 6 cards. The only caveat is that we also need to be able to encode an offset of zero. Still, that means we only need 4 of the 6 possible permutations.
So, let $O(6)$ mean a zero offset, and $O(5)$ and $O(4)$ will be unused.
Thus, we will hide the "larger" of the two and encode the other three in the appropriate offset.
Example 2
Lets try with the following cards: 3 spades, 10 spades, 3 hearts, 7 diamonds, 2 clubs.
Notice we have 2 spades exactly 7 apart, so we must use the special encoding. Also, notice that the other 3 non-spades are all in the $[A-7]$ interval, so ignore the 2 of clubs and use the lower spade (3) as the first card. Lastly, notice that the 7 is 4 away from the 3, but the 3 is only 3 away from the 7 when you wrap around at 7 in the $[A-7]$ interval. Thus, the 3 is the "larger" of the two and will be the hidden card. We then use encoding $O(3)$ of the other three cards.
3 spades, 7 diamonds, 2 clubs, 10 spades
When the Magician sees this, he will notice that there are exactly two spades being shown and they are exactly 7 apart. He knows that the non-joker method applied to this will result in a third spade, and if we had 3 spades, we would have had a choice as to which spade we chose to hide. Thus, we wouldn't have needed to show exactly two spades 7 apart. Therefore, the magician correctly infers that this is the special case of all four suits represented with exactly 2 spades 7 apart.
Immediately, the magician can deduce that the suit of the hidden card is hearts because that is the only suit not present in the displayed cards. He also recognizes $O(3)$ of the last three cards.
Now, since the lower of the two spades is the first one, the magician knows that the missing card is in the $[A-7]$ interval. Also, he sees that the other two non-spade cards are a 2 and a 7. Since both are in the $[A-7]$ interval, he ignores the lower(2) and uses the higher (7). Counting up $O(3) \implies +3$ from 7 within the $[A-7]$ interval gets 3.
Thus, the missing card is the 3 of hearts!
Intuitively, one can see that the 53 card solution should easily scale up to a 56 card solution by adding a joker to each suit instead of just spades. Assuming that the jokers can be differentiated from each other (thus, deterministically placed in a suit), it does, with one minor exception; when there are 2 cards in each suit exactly 7 apart. For example, the Ace/8 of hearts, the 2/9 of diamonds, and the 6 of clubs.
However, since there are unused orderings, we can use one of them to get the solution.
So, lets break down the strategy again:
3 or more cards in the same suit
Use the non-joker solution on one of the pairs which does not require that the pair exactly 7 apart are shown to the magician. Since there are 3 possible pairings, this is always possible.
Suited cards not 7 apart
Simply use the non-joker solution on the two suited cards.
One set of suited cards 7 apart
Use the special strategy from the previous section with this suit instead of spades. The key differences are:
- Any suit can be used to indicate the special case, not just spades
- the intervals are now $[Ace-7]$ and $[8-King,Joker]$; the second interval now has an extra card. This is OK since this simply makes both intervals the same size whereas before the $[8-King]$ interval was 1 shorter.
Two sets of suited cards 7 apart
For this scenario, you have 2 suits, each with 2 cards 7 apart. The fifth card is from a third suits.
The Joker-less strategy cannot be used since any two cards of the same suit are too far apart. The special strategy from before cannot be used because there would be no way for the magician to guess the right suit.
Thus, we need to use one of the unused orderings from that strategy, $O(4)$.
First, pick one of the suits which has 2 cards 7 apart, it doesn't matter which. One of them will be the hidden card. The other suit which has the 2 cards 7 apart will be used to tell the magician that this is a special case the same as before. The only difference is the meaning of the first card, and $O(4)$ will allow the magician to guess the hidden card.
The magician will see the two cards of the same suit 7 apart, one in the first position, and know it is the special case. He will then see $O(4)$ and know that this is the extra special case of two sets of suited cards 7 apart. Thus, he will know that the hidden card is 7 from one of the two other cards shown.
We will use the first card to tell the magician which - if we use the lower card as the first, then it is the lower of the other two cards which the magician will add 7 to. Otherwise, it is the higher.
Example 3
Lets say the cards are 2 Hearts, 9 Hearts, 3 Diamonds, 10 Diamonds, 6 Clubs.
This is the extra special case. We will first randomly pick one of the hearts or diamonds as the hidden card; it doesn't matter which because we will be able to encode enough information to tell the magician which. So lets say we pick the 3 of Diamonds as the hidden card.
We need the two Hearts to indicate the special case. Since the 10 (of Diamonds) is higher than the 6 (of Clubs), we will use the higher heart as the first card, and $O(4)$ for the rest.
9 Hearts, 6 Clubs, 10 Diamonds, 2 Hearts
The magician immediately sees the two hearts are 7 apart, so knows this is a special case. When he sees $O(4)$, he knows this is the extra special case. Of the two hearts, he sees the higher is the first, thus, the missing card is 7 from the higher of the two other cards - the 10 of Diamonds. So, counting forward 7 (Remember the Joker of Hearts!) gives Jack, Queen, King, Joker, Ace, Two, Three.
Thus, the missing card is the 3 of Diamonds!
No comments:
Post a Comment