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(2): please read by Ken Haley)

OK, Ady, I've found a failing case for your algorithm.

Suppose the audience choices are : C chooses 100, D chooses 20, E chooses 80, and F chooses 60.  When arranged in sequence the audience members are DFEC, and the numbers are 20, 60, 80, 100.  The only gap of 24 or more is between 20 and 60.  DFEC is the 20th permutation of the table you said A should memorize (if it's not, change the audience selection to get to the 20th permuation, but I think this is it).  So B finds card 40 and adds it to the original set of 4 cards, shuffles all 5 and gives them to A.

A now sorts the cards he's been given and sees that they are 20, 40, 60, 80, 100.  All the gaps are equal.  How is A supposed to know which card is the one B inserted?

 

Posted by Ken Haley on 2007-05-12 18:46:37