|
||
|
Title: 5 card trick redux Post by tim on Aug 22nd, 2002, 12:09am 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. |
||
|
Title: Re: 5 card trick redux Post by NickH on Aug 23rd, 2002, 2:54pm 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 |
||
|
Title: Re: 5 card trick redux Post by tim on Aug 23rd, 2002, 8:27pm 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 :-/ |
||
|
Title: Re: 5 card trick redux Post by TimMann on Sep 9th, 2002, 9:49pm 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. |
||
|
Title: Re: 5 card trick redux Post by william wu on Sep 10th, 2002, 12:05am 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. |
||
|
Title: Re: 5 card trick redux Post by tim on Sep 10th, 2002, 12:35am Quote:
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 :) |
||
|
Title: Re: 5 card trick redux Post by william wu on Sep 10th, 2002, 2:04am 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:
Ahh. This is very clear, thanks! :) |
||
|
Title: Re: 5 card trick redux Post by Crucio on Sep 24th, 2002, 9:36pm 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 |
||
|
Title: Re: 5 card trick redux Post by zeb on Jul 8th, 2003, 6:54am 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. |
||
|
Title: Re: 5 card trick redux Post by rmsgrey on Jul 14th, 2003, 4:51am 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... |
||
|
Title: Re: 5 card trick redux Post by zeb on Jul 16th, 2003, 1:58pm 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. |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |