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 Joel)

"So, the question now is do we have a method that works when there are 124 cards?"

Well, Ady's does not always work, even with 124 cards.

I've modified my program to have a variable number of choices for the card (variable called chc, for choices), rather than a hard-coded 100:

match$ = "1234,1243,1324,1342,1423,1432,2134,2143,2314,2341,2413,2431,"
match$ = match$ + "3124,3142,3214,3241,3412,3421,4123,4132,4213,4231,4312,4321"
chc = 200

CLS
DO
  REDIM taken(chc)
  FOR i = 1 TO 4
   DO
    n = INT(RND(1) * chc + 1)
    IF taken(n) = 0 THEN cd(i) = n: orig(i) = n: taken(n) = 1: EXIT DO
   LOOP
  NEXT

  j = 0
  FOR i = 1 TO chc
    IF taken(i) THEN
      j = j + 1
      cd(j) = i
    END IF
  NEXT

  seq$ = ""
  FOR i = 1 TO 4
    FOR j = 1 TO 4
      IF orig(i) = cd(j) THEN seq$ = seq$ + LTRIM$(STR$(j))
    NEXT
  NEXT

  Z = (INSTR(match$, seq$) + 4) / 5
  FOR i = 1 TO 4
    PRINT orig(i);
  NEXT
  PRINT Z

  cd(5) = cd(1) + chc
  FOR i = 1 TO 4
   IF cd(i + 1) - cd(i) > 24 THEN ak = cd(i): EXIT FOR
  NEXT
  newNumb = ak + Z

  s = 1
  FOR r = 1 TO 5
   IF newNumb < cd(s) THEN
     recd(r) = newNumb
     newNumb = 99999
   ELSE
     recd(r) = cd(s)
     s = s + 1
   END IF
  NEXT

  recd(6) = recd(1) + chc: recd(7) = recd(2) + chc
  'FOR i = 1 TO 7
  ' PRINT recd(i);
  'NEXT
  'PRINT
  FOR i = 2 TO 6
    diff = recd(i + 1) - recd(i - 1)
    IF diff >= 25 THEN ak2 = recd(i - 1): Z2 = recd(i) - ak2: EXIT FOR
  NEXT
  PRINT ak; Z, ak2; Z2;
  oCt = oCt + 1
  IF ak = ak2 AND Z = Z2 THEN PRINT :  ELSE PRINT " X": badCt = badCt + 1
  PRINT badCt / oCt
  REM
LOOP

It also keeps track of how many went bad as a fraction of the total number tried.

When a 100-card deck is used, the decoding gives a wrong result about 39% of the time. With 124 cards it goes wrong about 33% of the time. When 200 cards are used wrong results come about 22% of the time. Skipping ahead to a 500-card deck, the error rate is down to about 9%. With 1000 cards, we can get down to about 5% error rate.

Surely at some point there must be some other algorithm that would work with certainty, but it looks as if this one merely asymptotically approaches zero errors without actually getting there.

Posted by Charlie on 2007-05-13 11:17:20