Author |
Topic: 5 card trick redux (Read 2683 times) |
|
tim
Junior Member
Posts: 81
|
 |
5 card trick redux
« on: Aug 22nd, 2002, 12:09am » |
 Quote  Modify
|
One nifty feature about this problem is that the information-theoretic maximum deck size can actually be achieved in practice.
I proved this by brute force, using a computer to enumerate all possible card combinations. I'm still looking for a neat encoding method that a human might be able to use.
|
| « Last Edit: Sep 1st, 2003, 7:36pm by Icarus » |
 IP Logged |
|
|
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
|
Re: 5 card trick redux
« Reply #1 on: Aug 23rd, 2002, 2:54pm » |
Quote Modify
|
It's not too difficult to figure out that the information-theoretic maximum deck size is 124.
Having been astonished by the solution to the original problem, I can only say the solution to the maximal problem, given in the paper referenced by Freddy Mercury, is simply mind-blowing.
Nick
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: 5 card trick redux
« Reply #2 on: Aug 23rd, 2002, 8:27pm » |
Quote Modify
|
Bugger 
I actually thought of that technique. Due to a flaw in my arithmetic, when I tried it out on a simpler problem of 3 cards from 8 I double-counted one of the reduced hands and hence rejected the method 
Thanks for the pointer, you've saved me a lot of time that would otherwise have been wasted 
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: 5 card trick redux
« Reply #3 on: Sep 9th, 2002, 9:49pm » |
Quote Modify
|
This one was really fun. My friends and I worked on the maximal sized deck version for a while back a few years ago when I first heard about the problem, but I don't think any of us solved it -- I certainly didn't. With the additional push of having it posed here, I came up with the solution, the same pretty method of doing the trick as in the Kleber paper. It was very satisfying.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
 |
Re: 5 card trick redux
« Reply #4 on: Sep 10th, 2002, 12:05am » |
Quote Modify
|
I'm confused by this problem, despite the papers I've collected on the subject. Admittedly I probably didn't spend enough time combing through them, but as a full-time student my time is limited. Here's what I don't understand. It's pretty clear how to get the number 124: there are C(5,4) ways to choose 4 cards out of 5, and then there are 4! ways to permute those 4 chosen cards. So 4!*C(5,4) = 120. Thus the maximum deck size = 120 + 4 = 124. Now, why is actually pulling off the trick a nontrivial task? Couldn't I just make a huge table with all 120 possible permuted combinations in the left-hand column, and all their one-to-one mappings to the set {1, 2, 3, ... , 120 } in the right-hand column? Then the trick can be performed as long as magicians A and B both have this table.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: 5 card trick redux
« Reply #5 on: Sep 10th, 2002, 12:35am » |
Quote Modify
|
Quote:| Couldn't I just make a huge table with all 120 possible permuted combinations in the left-hand column, and all their one-to-one mappings to the set {1, 2, 3, ... , 120 } in the right-hand column? |
|
The main problem is that for any given set of 4 cards received, there are only 24 permutations, not 120.
A simpler example would be to construct such a table for the case of selecting 3 cards from 8. Try doing it by trial-and-error. 
It is non-trivial to show that of the 1:1 mappings between P(124,4) and C(124,5), there exists one such that for each permutation, all the cards in that permutation are also present in its corresponding combination.
Once you've proven that, then comes the task of finding a sufficiently regular mapping that the magician doesn't have to brute-force memorise a table with more than two hundred million entries 
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: 5 card trick redux
« Reply #6 on: Sep 10th, 2002, 2:04am » |
Quote Modify
|
I see. Although magician A has C(5,4).4! ways of encoding information at his or her disposal, the associate magician who receives the 4 cards does not directly know what the fifth card was, so it's not clear how to decode the information hidden in the C(5,4) term.
Quote:
It is non-trivial to show that of the 1:1 mappings between P(124,4) and C(124,5), there exists one such that for each permutation, all the cards in that permutation are also present in its corresponding combination.
Once you've proven that, then comes the task of finding a sufficiently regular mapping that the magician doesn't have to brute-force memorise a table with more than two hundred million entries
|
|
Ahh. This is very clear, thanks!
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Rajan
Newbie
Gender:
Posts: 5
|
|
Re: 5 card trick redux
« Reply #7 on: Sep 24th, 2002, 9:36pm » |
Quote Modify
|
Hello all,
My approach to solve this problem may be crude, cause i didnt analyze whether this problem can be done or not, or for how many cards can it be really done. I just went out and tried to figure out a way to do it. Here goes....
I got the point that B can address 24 cards given the information in the 4 cards that he has. Now, what does A do to Bring the 5th card into the domain of these 24 addressable cards. He must choose the 5th card wisely!! (what the hell, too damn obvious).
Imagine the 52 cards on the number line. in ascending order.
(diamond of A),(club of A),(heart of A),(spade of A),(diamond of 2),.....,(spade of king).
Now visualize the 5 cards on the number line. A and B decide beforehand that A will give an index number using the 4 cards and B will start the counting from the smallest card that he has. Using this method B can point to any card that is within 24 points of the lowest card that has been given to him.
The lowest card that A can give B is either the lowest of the 5 cards or the second lowest (he has to keep one of the five). If the distance on the number line between the lowest card and any other is less than 24 then it is very clear that B will be able to tell the card. Now, if the distance between the lowest and the second lowest card is more than 24 we cannot give B the lowest card, so we simply leave it out and give the others and B can do loopback while counting from (spade of King) to (diamond of A). Since distance between the first 2 cards was more than 24 in the forward direction, it must be less than 24 in the loopback path, hence the card is addressable.
Sorry for not being to able to tell you my thinking process ( cause there simply is none, it was kinda brute force ). Kept looking around for the answer until i got it!
Do you people have a different answer?
Crucio
|
|
IP Logged |
|
|
|
zeb
Newbie
Gender:
Posts: 3
|
|
Re: 5 card trick redux
« Reply #8 on: Jul 8th, 2003, 6:54am » |
Quote Modify
|
This seems only to show more generally (without use of suits) that the trick can be done with 52 cards. I am not convinced that it is possible to do this with more than 52 cards.
In any case, I think that 124 cards is too many. Since the 5th card is unknown to one of the magicians, it cannot be used to convey as much information as the others which are know by all. Careful selection of this card can increase what information you have (doubling the number of things that 4 cards can tell you in the case of the standard deck (or any 52 card deck)).
If anyone can convince me that it can be done with more than 52, I would be happy, but I am not so sure.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: 5 card trick redux
« Reply #9 on: Jul 14th, 2003, 4:51am » |
Quote Modify
|
This may be missing something obvious, but given 5 cards, you have a choice of 120 possible moves you can make - the fifth card in the permutation is defined by the choice of the first four, so each permutation produces a distinct move, so you can, in theory, indicate any of 120 possibilities plus eliminate the 4 you hand over. As mentioned above, the only hard parts are proving that you can map the permutations of 4 of 124 cards onto the combinations of 5 of 124 with each permutation using a subset of the corresponding combination, and finding such a mapping with a sufficiently low information content to be memorisable by mere mortals...
|
|
IP Logged |
|
|
|
zeb
Newbie
Gender:
Posts: 3
|
|
Re: 5 card trick redux
« Reply #10 on: Jul 16th, 2003, 1:58pm » |
Quote Modify
|
Well, since my last post on the subject, I have been thoroughly convinced that the trick can be done with a 124 card deck. There is even a good algorithm by which the trick can be perfomed without a great deal of memorization. I am almost ready to start trying to perform the trick (the hard part is getting a 124 card deck).
I won't go into how it is done, I am affraid I didn't get too far on my own trying to figure it out. There is a link to a very nice paper onthe subject in the forum on the original 5 card trick. There you can find a proof that 124 is indeed the maximal deck for a 5 card trick and some generalization to an n card hand.
This is a great trick. It really is amazing how much information can be conveyed by the choice of the hidden card.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print