Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The Original Fitch Cheney puzzle goes like this:

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.

The solution to this is:

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.

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.

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.

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).

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)).

My question is this: With the audience choosing n 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?

share|improve this question
3  
It might help to explain the standard solution to this puzzle. –  Michael Lugo Apr 7 '10 at 22:01
    
@Michael: spelman.edu/~colm/cheney.html –  Steve Huntsman Apr 7 '10 at 22:18
    
1  
As noted in Kleber's paper, unique strategies just correspond to perfect matchings in the corresponding bipartite graph. He notes that there are "at least n!" of them, but I'm not sure what the more precise answer is. Googling suggests that counting perfect matchings in bipartite graphs is difficult, but getting an approximation is easy. This situation might be simpler, though, because the graph has a high degree of symmetry (it's n!-regular, for one thing). –  Jonah Ostroff Apr 8 '10 at 2:19
add comment

1 Answer

up vote 5 down vote accepted

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.)

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.

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.

We can get a much better lower bound if this paper 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.)

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.

share|improve this answer
    
Hm. Not sure what's happening with the LaTeX in my second paragraph. Underscores are being read as italics, I guess? If someone else can help me fix it, that would be grand. –  Jonah Ostroff Apr 8 '10 at 14:44
    
Put backticks around code that is being parsed weirdly; that usually fixes it. –  Tom Church Apr 8 '10 at 14:46
    
Thanks, that seems to have done it. –  Jonah Ostroff Apr 8 '10 at 14:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.