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 A new approach by Jer)

No approach can work.

Any approach will result in not only knowing the order of the cards but what those cards are, which is part of the information conveyed by the cards presented to A. There's no way of avoiding that part of the information from being part of what's encoded.  There are only C(100,5) card sets that might be presented to A.  This is smaller than the P(100,4) choices that the audience may have made.  The premise of the problem is that the choice of one of the C(100,5) is enough to differentiate among the P(100,4) possibilities (again, I repeat, that there's no way of avoiding learning this along with the sequence of matches to the audience members, so this must be part of the encoded information,there's no way around it).

The pigeonhole principle precludes a solution by this mathematical method alone.

Posted by Charlie on 2007-05-14 23:53:55