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: please read by Ady TZIDON)

Charlie's argument is irrefutable.  The fact is there are 94,109,400 ordered ways (permutations) in which 4 audience members can select 4 cards.  When A looks at the cards, a card has been added by B and they've been shuffled.  Thus the number of distinct arrangements of cards that can be given to A is the number of combinations (not permutations) of the 5 cards selected from 100.  Thus A can receive no more than 75,287,520 distinct messages when he receives the 5 cards.  So it isn't possible for all 94 million+ different possibilities of the original 4 persons' selections to be conveyed with 5 shuffled cards, since there are only 75 million+ ways to do the latter.

Ady, there must be something wrong with your algorithm--I'm sure if I studied it long enough, I could find two different sets of choices from the audience which, after B follows your method to add his 5th card, results in the same set of 5 cards, leaving A no way to determine which of the two cases it must be.

The only way this trick can be pulled off 100% of the time is using an additional trick, wherein A receives more information than just the 5 shuffled cards.

Posted by Ken Haley on 2007-05-12 18:29:47