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

Home > Logic
5 Cards Magic Trick Redux (Posted on 2009-06-05) Difficulty: 3 of 5
This is a magic trick performed by two magicians, Alice and Bob, with one shuffled deck of N unique cards. (Nothing is mentioned about suits; you may consider these cards to be simply enumerated from 1 to N.)

Alice asks a member of the audience, Carol, to randomly select 5 cards out of a deck. Carol then returns her chosen 5 cards to Alice. After looking at the 5 cards, Alice picks one of the 5 cards and gives it back to Carol.

Alice then arranges the other four cards in some way, and gives them to Bob in a neat, face-down pile. Bob examines these 4 cards and determines what card is in Carol's hand (the missing 5th card). Carol is astonished!

What is the largest number of cards N that the deck can contain before the trick is no longer performable? Prove it.

How specifically do you execute the trick on a deck of maximal size N?

See also "5 Cards Magic Trick".

---------------------------------------------------------------

Note: There's no secretive message communication in the solution, like encoded speech or ninja hand signals or ESP or whatever ... the only communication between the two magicians is in the logic of the 4 cards transferred from A to B. Think of these magicians as mathematicians.

No Solution Yet Submitted by Assaf    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution a way | Comment 2 of 3 |

I don't know a way of proving analytically that it's possible to come up with a method for the 124-card theoretical limit, but I wrote a program to verify its possibility, in VB 5.0:

Private Sub cmdStart_Click()
  Kill "cardtrik.bin"
  Open "cardtrik.bin" For Binary As #2
  Open "cardtrk1.bin" For Binary As #3
  Open "cardtrk2.bin" For Binary As #4
  currf = 3
  ch$ = " "
  For c1 = 1 To 120
   If c1 = 51 Then currf = 4
   For c2 = c1 + 1 To 121
   txtProgress.Text = Str(c1) + Str(c2)
   For c3 = c2 + 1 To 122
   For c4 = c3 + 1 To 123
   For c5 = c4 + 1 To 124
   DoEvents
    done = 0
    n = filePosn(c1, c2, c3, c4)
    Get #2, n, ch$
    If ch$ < Chr$(24) Then
     ch$ = Chr$(Asc(ch$) + 1): Put #2, n, ch$: done = 1
     Put #currf, , Chr$(c1) + Chr$(c2) + Chr$(c3) + Chr$(c4) + Chr$(c5)
     Put #currf, , Chr$(c1) + Chr$(c2) + Chr$(c3) + Chr$(c4) + ch$
    End If
    If done = 0 Then
        n = filePosn(c1, c2, c3, c5)
        Get #2, n, ch$
        If ch$ < Chr$(24) Then
         ch$ = Chr$(Asc(ch$) + 1): Put #2, n, ch$: done = 1
         Put #currf, , Chr$(c1) + Chr$(c2) + Chr$(c3) + Chr$(c4) + Chr$(c5)
         Put #currf, , Chr$(c1) + Chr$(c2) + Chr$(c3) + Chr$(c5) + ch$
        End If
    End If
    If done = 0 Then
        n = filePosn(c1, c2, c4, c5)
        Get #2, n, ch$
        If ch$ < Chr$(24) Then
         ch$ = Chr$(Asc(ch$) + 1): Put #2, n, ch$: done = 1
         Put #currf, , Chr$(c1) + Chr$(c2) + Chr$(c3) + Chr$(c4) + Chr$(c5)
         Put #currf, , Chr$(c1) + Chr$(c2) + Chr$(c4) + Chr$(c5) + ch$
        End If
    End If
    If done = 0 Then
        n = filePosn(c1, c3, c4, c5)
        Get #2, n, ch$
        If ch$ < Chr$(24) Then
         ch$ = Chr$(Asc(ch$) + 1): Put #2, n, ch$: done = 1
         Put #currf, , Chr$(c1) + Chr$(c2) + Chr$(c3) + Chr$(c4) + Chr$(c5)
         Put #currf, , Chr$(c1) + Chr$(c3) + Chr$(c4) + Chr$(c5) + ch$
        End If
    End If
    If done = 0 Then
        n = filePosn(c2, c3, c4, c5)
        Get #2, n, ch$
        If ch$ < Chr$(24) Then
         ch$ = Chr$(Asc(ch$) + 1): Put #2, n, ch$: done = 1
         Put #currf, , Chr$(c1) + Chr$(c2) + Chr$(c3) + Chr$(c4) + Chr$(c5)
         Put #currf, , Chr$(c2) + Chr$(c3) + Chr$(c4) + Chr$(c5) + ch$
        End If
    End If
    If done = 0 Then Print "bad": Exit Sub
   Next
   Next
   Next
   Next
  Next
  Print "end"
End Sub

Function filePosn(a, b, c, d)
 filePosn = (a - 1) * 1906624 + (b - 1) * 15376 + (c - 1) * 124 + d - 1
End Function

The file cardtrik.bin is used to keep track of which subsets of four have been used how many times. A given subset can be used only 24 times and then a different subset must be used.

The cardtrk1.bin and cardtrk2.bin are used to actually write each encoding, using one byte of binary to represent each of the five cards to be represented, one byte to represent each of the four cards used in the subset and one byte to represent which of the 24 permutations of those four is to be used for this particular combination of five cards to be represented. Two files are used as apparently VB 5.0 can't handle binary files over 2 gigabytes. Combinations with no card lower than 51 seemed a good transition point to the second file.

The program did indeed print the word "end" on the form rather than the "bad" that would indicate that some combination of five couldn't be encoded because all the possible encodings were taken by a previous combination. The two cardtrk files contain the parallel columns of represented combinations and their encoding.

A QuickBasic program can present the results by reading the files and converting to decimal:

DEFDBL A-Z
DATA 2090412600, 161087640

READ max1, max2
max1 = max1 / 10: max2 = max2 / 10
max = max1 + max2

OPEN "cardtrk1.bin" FOR BINARY AS #1
OPEN "cardtrk2.bin" FOR BINARY AS #2

r$ = SPACE$(10)
rec1 = 1
DO
  CLS
  FOR recNo = rec1 TO rec1 + 45
    rNo = recNo: fileNo = 1
    IF rNo > max1 THEN rNo = rNo - max1: fileNo = 2

    rec = rNo
    GET #fileNo, (rec - 1) * 10 + 1, r$
    FOR i = 1 TO 10
      PRINT USING "####"; ASC(MID$(r$, i, 1));
    NEXT
    PRINT
  NEXT
  DO: a$ = INKEY$: LOOP UNTIL a$ > ""
  rec1 = rec1 + 46
LOOP UNTIL a$ = CHR$(27)
CLOSE

Excerpts of the resulting table of correspondences between 5-card set and the 4-card code follow to get an idea of how the encoding goes:

five card combination            4-card     which
---------------------        --- subset---  permutation
   1   2   3   4   5         1   2   3   4   1
   1   2   3   4   6         1   2   3   4   2
   1   2   3   4   7         1   2   3   4   3
   1   2   3   4   8         1   2   3   4   4
   1   2   3   4   9         1   2   3   4   5
   1   2   3   4  10         1   2   3   4   6
   1   2   3   4  11         1   2   3   4   7
   1   2   3   4  12         1   2   3   4   8
   1   2   3   4  13         1   2   3   4   9
   1   2   3   4  14         1   2   3   4  10
   1   2   3   4  15         1   2   3   4  11
   1   2   3   4  16         1   2   3   4  12
   1   2   3   4  17         1   2   3   4  13
   1   2   3   4  18         1   2   3   4  14
   1   2   3   4  19         1   2   3   4  15
   1   2   3   4  20         1   2   3   4  16
   1   2   3   4  21         1   2   3   4  17
   1   2   3   4  22         1   2   3   4  18
   1   2   3   4  23         1   2   3   4  19
   1   2   3   4  24         1   2   3   4  20
   1   2   3   4  25         1   2   3   4  21
   1   2   3   4  26         1   2   3   4  22
   1   2   3   4  27         1   2   3   4  23
   1   2   3   4  28         1   2   3   4  24
   1   2   3   4  29         1   2   3  29   1
   1   2   3   4  30         1   2   3  30   1
   1   2   3   4  31         1   2   3  31   1
   1   2   3   4  32         1   2   3  32   1
   1   2   3   4  33         1   2   3  33   1
  
   ,,,


  
   so you see that once the 24 possible permutations of 1,2,3,4 are exhausted, it starts to use 1,2,3,highest number, all in their first permutation.
  
 

  ...
 
 
   1   2   3   4 122         1   2   3 122   1
   1   2   3   4 123         1   2   3 123   1
   1   2   3   4 124         1   2   3 124   1
   1   2   3   5   6         1   2   3   5   1
   1   2   3   5   7         1   2   3   5   2
   1   2   3   5   8         1   2   3   5   3
   1   2   3   5   9         1   2   3   5   4
   1   2   3   5  10         1   2   3   5   5
   1   2   3   5  11         1   2   3   5   6
   1   2   3   5  12         1   2   3   5   7
   1   2   3   5  13         1   2   3   5   8
   1   2   3   5  14         1   2   3   5   9
   1   2   3   5  15         1   2   3   5  10
   1   2   3   5  16         1   2   3   5  11
     
   ...     
  


   when 124 is reached and 5 is again used but not as the highest number, 1,2,3,5 starts to be used, in its 24 permutations. And when those are exhausted, we again use the highest number, but this time with the second permutation of each subset.  Note that 1,2,3,29 is not needed below as 29 already fits in with the 24th permutation of 1,2,3,5:
 

  
   ...
  
   1   2   3   5  27         1   2   3   5  22
   1   2   3   5  28         1   2   3   5  23
   1   2   3   5  29         1   2   3   5  24
   1   2   3   5  30         1   2   3  30   2
   1   2   3   5  31         1   2   3  31   2
   1   2   3   5  32         1   2   3  32   2
   1   2   3   5  33         1   2   3  33   2
   1   2   3   5  34         1   2   3  34   2
   1   2   3   5  35         1   2   3  35   2
   1   2   3   5  36         1   2   3  36   2
   1   2   3   5  37         1   2   3  37   2
   1   2   3   5  38         1   2   3  38   2
  
   ...
  
   1   2   3   5 123         1   2   3 123   2
   1   2   3   5 124         1   2   3 124   2
   1   2   3   6   7         1   2   3   6   1
   1   2   3   6   8         1   2   3   6   2
   1   2   3   6   9         1   2   3   6   3
   1   2   3   6  10         1   2   3   6   4
  
   ...
  
   1   2   3   6  29         1   2   3   6  23
   1   2   3   6  30         1   2   3   6  24
   1   2   3   6  31         1   2   3  31   3
   1   2   3   6  32         1   2   3  32   3
   1   2   3   6  33         1   2   3  33   3
   1   2   3   6  34         1   2   3  34   3
  
   ...


  
   Note that we do eventually get to use that 1,2,3,29, 2nd and subsequent permutations.
 

  
   ...
                         
   1   2   3  28 123         1   2  28 123   1
   1   2   3  28 124         1   2  28 124   1
   1   2   3  29  30         1   2   3  29   2
   1   2   3  29  31         1   2   3  29   3
   1   2   3  29  32         1   2   3  29   4
   1   2   3  29  33         1   2   3  29   5
   1   2   3  29  34         1   2   3  29   6
  
   ...
  
 117 118 119 123 124       117 118 119 123  24
 117 118 120 121 122       117 118 120 121  22
 117 118 120 121 123       117 118 120 121  23
 117 118 120 121 124       117 118 120 121  24
 117 118 120 122 123       117 118 120 122  23
 117 118 120 122 124       117 118 120 122  24
 117 118 120 123 124       117 118 120 123  24
 117 118 121 122 123       117 118 121 122  23
 117 118 121 122 124       117 118 121 122  24
 117 118 121 123 124       117 118 121 123  24
 117 118 122 123 124       117 118 122 123  24
 117 119 120 121 122       117 119 120 121  22
 117 119 120 121 123       117 119 120 121  23
 117 119 120 121 124       117 119 120 121  24
 117 119 120 122 123       117 119 120 122  23
 117 119 120 122 124       117 119 120 122  24
 117 119 120 123 124       117 119 120 123  24
 117 119 121 122 123       117 119 121 122  23
 117 119 121 122 124       117 119 121 122  24
 117 119 121 123 124       117 119 121 123  24
 117 119 122 123 124       117 119 122 123  24
 117 120 121 122 123       117 120 121 122  23
 117 120 121 122 124       117 120 121 122  24
 117 120 121 123 124       117 120 121 123  24
 117 120 122 123 124       117 120 122 123  24
 117 121 122 123 124       117 121 122 123  24
 118 119 120 121 122       118 119 120 121  22
 118 119 120 121 123       118 119 120 121  23
 118 119 120 121 124       118 119 120 121  24
 118 119 120 122 123       118 119 120 122  23
 118 119 120 122 124       118 119 120 122  24
 118 119 120 123 124       118 119 120 123  24
 118 119 121 122 123       118 119 121 122  23
 118 119 121 122 124       118 119 121 122  24
 118 119 121 123 124       118 119 121 123  24
 118 119 122 123 124       118 119 122 123  24
 118 120 121 122 123       118 120 121 122  23
 118 120 121 122 124       118 120 121 122  24
 118 120 121 123 124       118 120 121 123  24
 118 120 122 123 124       118 120 122 123  24
 118 121 122 123 124       118 121 122 123  24
 119 120 121 122 123       119 120 121 122  23
 119 120 121 122 124       119 120 121 122  24
 119 120 121 123 124       119 120 121 123  24
 119 120 122 123 124       119 120 122 123  24
 119 121 122 123 124       119 121 122 123  24
 120 121 122 123 124       120 121 122 123  24
--------------------       ----- 4-card---  which  
five card combination            subset    permutation
                          
  

   I can't think of a good way of describing this schema or how it could be memorized sufficiently for Alice to encode and Bob to decode. Using 10 bytes per entry, with 225,150,024 entries, the table, as mentioned, takes over 2 gigabytes. Just doing a sequential search for the decoding takes a few minutes. (Encoding can be done with a binary search as the table is in the order of the 5-card combinations; of course it could be sorted to produce one for decoding, but then, I don't think the trick would go over well if the magician used a computer.)
  
   BTW, just to take one example of how to interpret the above:
  
 

  Suppose the permutations for A<B<C<D are:
   1: ABCD
   2: ABDC
   3: ACBD
   4: ACDB
   5: ADBC
   6: ADCB
   7: BACD
   ...
  


   then, 1,2,3,29, 6th permutation would be 1,29,3,2 (which is the ADCB for this subset).


  Posted by Charlie on 2009-06-06 00:31:41
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information