This is a magic trick performed by two magicians, Alice and Bob, with one shuffled deck of N unique cards. (Nothing is mentioned about suits; you may consider these cards to be simply enumerated from 1 to N.)

Alice asks a member of the audience, Carol, to randomly select 5 cards out of a deck. Carol then returns her chosen 5 cards to Alice. After looking at the 5 cards, Alice picks one of the 5 cards and gives it back to Carol.

Alice then arranges the other four cards in some way, and gives them to Bob in a neat, face-down pile. Bob examines these 4 cards and determines what card is in Carol's hand (the missing 5th card). Carol is astonished!

What is the largest number of cards N that the deck can contain before the trick is no longer performable? Prove it.

How specifically do you execute the trick on a deck of maximal size N?

See also "5 Cards Magic Trick".

---------------------------------------------------------------

Note: There's no secretive message communication in the solution, like encoded speech or ninja hand signals or ESP or whatever ... the only communication between the two magicians is in the logic of the 4 cards transferred from A to B. Think of these magicians as mathematicians.

When Alice communicates the identity of the withheld card to Bob by means of the four stacked cards, she also of necessity reveals the ones actually handed over, and thus has revealed the whole hand through this information. Thus there needs be as many codes (permutations of the four cards handed over -- P(N,4)) as there are possible sets of five cards that Bob needs to identify. Thus P(N,4) needs to be at least as great as C(N,5).

In the original puzzle, N was 52, and P(52,4) = 6,497,400 is more than sufficient to cover the C(52,5) =  2,598,960 possible sets of five that Bob needs to identify.

As N gets larger, both numbers get larger, but C(N,5) gets larger faster and eventually overtakes P(N,4). This happens at N = 124, where each is equal to 225,150,024. So at that value there are just as many encodings (sets of four cards with specified orderings), as there are sets of five cards to be encoded.

Beyond N = 124, there are more cases to encode than there are codes to handle them, so the trick is not performable for N > 124.

Is it performable for N = 124?

We can't just list the combinations in order in one column and the permutations in order in the other and use that set of pairings as the code. The very second entry shows why:

1, 2, 3, 4, 5  coded as 1, 2, 3, 4
1, 2, 3, 4, 6  coded as 1, 2, 3, 5

as there is no 5 available to pass from Alice to Bob in the second 5-card hand.

So a 1-to-1 correspondence must be made between the combinations of 124 taken 5 at a time and the permutations of 124 taken 4 at a time in such a way that the members of each permutation must be subsets of the combination they are representing.

A given subset can be present in only 4! = 24 coded stacks, but there are 120 combinations of 5 that use a given subset of 4, so those combinations must be represented by other subsets. Luckily there are 5 subsets of 4 for a given combination: leaving out any one of the five. And 5*24 = 120, so if we play our cards right we could work out a correspondence.

Posted by Charlie on 2009-06-05 15:35:09