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?



Generalization of Finch Cheney's 5 Card Trick
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](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHT-45SRMS1-9&_user=520880&_coverDate=01%2F31%2F1998&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000023460&_version=1&_urlVersion=0&_userid=520880&md5=aa3f297a22e5087962ec4c451b0cc68b) 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.


