All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Magic trick (Posted on 2007-05-11)
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.

 No Solution Yet Submitted by atheron Rating: 4.1667 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

Regardless of what algorithms are used for encoding and decoding the cards, the algorithm that A uses to decode the five cards he sees can be expressed as a table, with the cards seen in the left hand column and the identified sequence of four cards chosen by the 4 random audience members, on the right, such as below:

`cards that A sees      deduced sequence of first 4                      (the ones from the audience--not B)`
`1 2 3 4 5                  2,3,4,51 2 3 4 6                  1,2,3,41 2 3 4 7                  1,2,4,31 2 3 4 8                  1,3,2,41 2 3 4 9                  1,3,4,21 2 3 4 10                 1,4,2,3  ...          ...           ... `
`  ...          ...           ...95 97 98 99 100            100,99,98,9796 97 98 99 100            99,98,97,96`

(If it is decided that certain possibilities, such as 1 2 3 4 5 will never be presented to A--as B will never choose to complete any of the subsets in that way--, so the right-hand entry for that line will be left blank, then the below argument is all that much stronger.)

Clearly there must be P(100,4) = 94,109,400 possibilities on the right hand column that depend on the left hand column, not just the 4! = 24 entries that are for example entries 2 thru 25, devoted to identifying the sequencing of cards 1 thru 4. This is the big picture, of all the possibilities that the four audience members might throw.

But the left hand column limits this to C(100,5) = 75,287,520 possible rows to this table. These are the only possible sets of cards that A could possibly see.  It has to cover all the permutations the audience might set from among the 100 cards.  There are not enough rows to cover them all, that is, not enough sets of cards that might be presented to A to allow him to determine what card each of the four audience members selected.

 Posted by Charlie on 2007-05-12 10:20:26

 Search: Search body:
Forums (0)