Two magicians A and B perform the following trick:

A leaves the room and B chooses 4 members from the audience at random. Each member chooses a card numbered from 1 to 100 (each chooses a different card) and after B has seen their cards he chooses a card from the remaining deck of cards. The 5 chosen cards are shuffled by an audience member and handed to A who just returned to the room. Prove that A is able to figure out which cards each member picked. Consider that the chosen members form a row and e.g. the leftmost member picks the first card and the rightmost member (B) picks the last card.

There are P(100,4) = 94,109,400 possible sequences that A might be required to state.  There are only C(100,5) = 75,287,520 possible sets of cards that A might be given--not enough to elicit one of the 94,109,400 possible sequences he might be required to say.  Some other clue must be given--perhaps B hands the packet either face down or face up as one more bit (yes, binary digit) of information doubling the number of clue possibilities to 150,575,040, which is more than the number of sequences that need to be elicited.

Obviously the code (5 cards plus one more bit) must include the particular combination of cards chosen by the audience. I don't know if a feasible coding scheme can be worked out--presumably it can.

Posted by Charlie on 2007-05-11 13:39:41