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?
Best Answer
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.