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.
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 |
a way
