Generalization of Finch Cheney's 5 Card Trick - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T18:48:23Z http://mathoverflow.net/feeds/question/20667 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/20667/generalization-of-finch-cheneys-5-card-trick Generalization of Finch Cheney's 5 Card Trick Dan 2010-04-07T21:43:25Z 2010-04-08T14:54:16Z <p>The Original Fitch Cheney puzzle goes like this:</p> <blockquote> <p>A Volunteer from the crowd chooses any five cards at random from a deck, and hands them to you so that nobody else can see them. You glance at them briefly, and hand one card bakc, which the volunteer then places face down on the table to one side. You quickly place the remaining four cards face up on the table, in a row from left to right. Your confederate, who has not been privy to any of the proceedings so far, arrives on the scene, inspects the faces of the four cards, and promptly names the hidden fifth card.</p> </blockquote> <p>The solution to this is:</p> <blockquote> <p>One of the 4 suits must be represented 2 times in your set of 5 cards due to the pigeon hole principle. Consider the 13 cards of that suit A=1,... K=13 to be arranged in a clockwise circle. We can see that the cards are at most 6 away from each other, meaning counting clockwise one of them lies at most 6 vertices past the other. Use the "higher" one as the hidden card and place the "lower" one as the first card face up on the table.</p> <p>Now, using an established value for all 52 cards in the deck, the remaining 3 cards can be placed in 6 orders, Low-Middle-High=1, LHM=2, MLH=3, MHL=4, HLM=5, and HML=6, and give each one of these a value of +1,..., +6 from the first card.</p> <p>For example, Jc, 2c, 3h, 4d, 2s are handed to you. Choosing the lower club, (2-Jack(11) Mod 13 is 4, so the Jack is the lower one and the 2 is +4 from the jack. Hide the 2c and place the Jc in the first spot. Then using MHL, our +4 value, we arrange the remaining 3 cards with the 3 first, than the 4, now the 2. This implies that the hidden card is a club, and it is +4 from the Jc in the first spot, so we know it is the 2c.</p> </blockquote> <p>The 124 card solution is discussed in the January 2001 issue of Emissary or Michael Kleber’s article in The Mathematical Intelligencer, Winter 2002 (which I don't have access to).</p> <p>It can be shown that with 5 cards there is a strategy to do the trick on a deck of size up to 124 cards (n!+(n-1)). </p> <p>My question is this: With the audience choosing <em>n</em> cards out of a deck of size (n!+(n-1)) and one card being hidden, how many unique strategies could the magician and the assistant use?</p> http://mathoverflow.net/questions/20667/generalization-of-finch-cheneys-5-card-trick/20735#20735 Answer by Jonah Ostroff for Generalization of Finch Cheney's 5 Card Trick Jonah Ostroff 2010-04-08T14:42:45Z 2010-04-08T14:54:16Z <p>Kleber's paper will certainly point you in the right direction if you can find it. (I have a printed out copy, and I don't remember where on the web I got it. Sorry.)</p> <p>In it, he suggests thinking about a strategy as a pairing up of the $(n!+n-1)_{n-1}$ messages with the ${{n!+n-1}\choose n} = (n!+n-1)_{n-1}$ hands the audience can give you. Of course, you can only pair a message with one of the n! hands that contain its cards, and you can only pair a hand with one of the n! messages you can make with it. So this is just like finding a perfect matching on an n!-regular bipartite graph, and by Hall's Marriage Theorem this is possible.</p> <p>The bipartite graph you draw here is quite symmetric: aside from being n!-regular, it's also vertex transitive, so any of the n! edges you could choose from a particular vertex v are part of some perfect matching (since one of them is). This is where Kleber's claim that there are "at least n!" strategies come from.</p> <p>We can get a much better lower bound if <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6WHT-45SRMS1-9&amp;_user=520880&amp;_coverDate=01%2F31%2F1998&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_acct=C000023460&amp;_version=1&amp;_urlVersion=0&amp;_userid=520880&amp;md5=aa3f297a22e5087962ec4c451b0cc68b" rel="nofollow">this paper</a> is to be believed. Here it says there are at least $\left(\frac{(n!-1)^{n!-1}}{n!^{n!-2}}\right)^{{n!+n-1}\choose n}$ strategies, which for n=2 isn't very enlightening (it says there's at least one, when we know there are really two), but for n>2 puts our previous estimate to shame: with a three-card hand (and thus an eight-card deck), we get at least 2.54x10^21 strategies, a number so fantastically larger than our previous estimate of 6 that I'm still a little bit in shock. (It is, at least, many orders of magnitude lower than the naive upper bound of 6^56, where for each of the 3-subsets of 8 we choose one of the possible messages it could send without worrying about overlap with other hands.)</p> <p>Anyway, I haven't read the linked paper, but the abstract suggests we might not get a much better lower bound than this. To improve, one might look for results on vertex transitive k-regular bipartite graphs, but I haven't found any.</p>