The Fitch Cheney Card Trick Extended

Question

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 1

Strategy without the Joker

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.

Adding the joker

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!

Solution for 56 Cards

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!

Answer 2

This made interesting reading this morning. :-) [Came here following a random link on StackExchange where I was getting some programming syntax help..]

I then followed the link in Trenin's answer to the paper http://www.nymphomath.ch/crypto/magie/cardTrick.pdf

In that paper someone was very excited to have worked out a way to support up to 124 cards with 5 cards... and that got me thinking about this more. Seems to me that the historical thinking/mechanism around this trick has effectively constrained the various solutions proposed.

So now I can boldly say that I have devised at least 2 different strategies where this trick could be done with just 2 extra cards instead of 4...and just to make things more fun, the AUDIENCE can choose which of the 3 cards they want to keep aside rather than the assistant. :-)

Not only that, we will even do the 3-card trick and almost support the magical "124" limit (we will support 120).

If you still insist upon giving the assistant 4 cards then we will comfortably be able to support a "deck" of up to 340 cards - ie 6 full decks each including 4 (unique) jokers (obviously each deck would need a unique coloured back, or varying (distinctive) card faces in order to distinguish it from the other decks).

In fact we could happily extend our 4-card trick to identify a card from a deck of 780 different cards (actually up to 2800 but now we'd just be showing off, and who can hold a deck that big anyway ? :-))

To be fair we couldn't cope with quite so many cards/variations if we had to do the trick exactly as described in this article, but I find that the "requirements" of the trick vary slightly depending on whose version you are reading, while retaining the same general requirements.

See for example the description in https://mathoverflow.net/questions/20667/generalization-of-finch-cheneys-5-card-trick ... so I am taking the slightly more permissive view with regard to exactly what the assistant does with the cards (remembering that this was initially an on-stage trick, so surely as long as we stick to the overall general requirements of the magician identifying the selected card as a result of walking in the room an examining the other cards on the table we have fulfilled the "requirements".)

Just to show that we are good sports, if the audience draws 4 cards altogether from the deck, and keeps 2, as long as you let my assistant replace the cards on the table after I have identified the first of your cards, I'll identify the other one as well. (He'll need to briefly hold your 2nd card of course before rearranging the other cards just to ensure that he has transferred enough "energy" from it to the cards that I will "read"... :-))

Or would you like to select 5 cards as in the original trick, keep 3 instead of 1, and then after I have identified the first one by examining the other 2, he will add the just-identified card to his table pile (because of course it also carries energy from being near the other 2 !) and then we will identify a 2nd-card. Finally we will identify your 3rd card and even tell you whether a man or a woman chose the card. Would that impress you ?

Maybe I will go become a magician... :-) I'm sure you'll work out as I did multiple ways this can be done. And if you can't I'll publish some here soon.