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.

(In reply to re: limitations by JayDeeKay)

"B doesn't need to encode all the P(100, 4) possibilities, just the 4! = 24 arrangements of the selected 4 cards, as Jer has observed. "

If A sees, for example, 17, 33, 54, 72 and 90, he must say some particular order (actually 5!, as he must choose which is the B-chosen card). Say this particular combination calls for 33,72,17,90 by the audience members, in that order, and 54 by B.  If he sees, for another example, 10, 34, 78, 80, 85, he must say some other particular order, say for example 34,10,78,85 by audience members in that order and 80 by B.

There are only 75,287,520 sets he might see, but 94,109,400 (or maybe it should be 9,034,502,400, but its definitely at least 94,109,400) things he could have to say in response, so there are not enough triggers for each of the possible things he might have to say.

 

Edited on May 11, 2007, 3:53 pm

Posted by Charlie on 2007-05-11 15:47:14