Five Card Magic Trick with $N$ card Deck

Question

Last week, I saw a magic show, and was the volunteer for climactic act. The magician introduced this act by talking about the Fitch-Cheney card trick, but then explained that she was going to do an even more impressive trick. Namely, instead of using a $52$ card deck, she would use a larger deck, with $N$ cards, though she didn't say exactly how big $N$ was.

Here's what happened:

The magician left the room. An assistant asked me to look through the $N$ card deck, and pick out any $5$ cards. The assistant inspected the cards I chose, then gave one back to me, which I put in my pocket. He arranged the remaining four cards in a neat stack, and placed this stack face down on a table. The magician returned, inspected the stack, and successfully guessed the card in my pocket.

What is the largest value of $N$ for which the trick can be performed? For that $N$, how is it done?

Note that there is no slight of hand or secret communication. Each card is distinct, the faces are rotationally symmetric, and the stack is placed at the exact same spot on the table every time the trick is performed. The assistant is only allowed to choose which card the volunteer gets ($5$ choices), then permute the four other cards ($4!=24$ choices).

---

^{Aside: From this question, we know $N=53$ is possible.}

Answer 1

Stealing from 2012rcampion's answer, we need to create a one-to-one mapping from five-card hands to four-card messages (four cards plus permutation). By symmetry, each four-card message can be mapped to an equal number of five-card hands, so by the regular version of Hall's Theorem there must exist such a one-to-one mapping (this is laid out in more detail in GentlePurpleRain's comment link).

Thus, the trouble is actually constructing a matching, and ideally doing so in a way that would work well as a magic trick. The following works for the former, and you can decide if it works for the latter.

---

Suppose the cards are numbered 0 to 123. Call the five cards, from smallest to largest, $c_0$, $c_1$, $c_2$, $c_3$, and $c_4$. To find the pocketed card, the assistant adds up the numbers on all five cards, reduces the answer modulo $5$ to get $S$, and then hands back $c_S$.

Now the magician can see four cards. Suppose these four cards sum to $S'$ modulo $5$. Suppose also she mentally removes these four cards from the deck and then relabels the remaining cards in order from $0$ to $119$ (call these "reduced numbers"). Then we have

the missing card must have a reduced number equivalent to $(-S')$ modulo $5$*.

This means there are only $24$ possibilities, and hence with a code that takes permutations of four cards to the set $\{1, 2, ..., 24\}$, the assistant can supply enough information for the magician to identify the card.

---

*This is a bit hard to see, so let's break it down into cases. If $c_0$ was removed, that means the sum of the five cards is $0$ mod $5$, and hence the missing card must be $-S'$ mod $5$ to counter the $S'$ sum of the other four cards. If $c_1$ was removed, then the missing card must have had a number of $-S' + 1$, but since it appears after $c_0$ that we mentally removed from the deck, it's reduced number is $-S' + 1 - 1 = -S'$. Similar logic shows this works for all five cases.

Answer 2

A slightly different way to think about this problem is that the magician is trying to guess which five-card hand was initially drawn from the deck. Since he can see the other four cards, this is the same as guessing the volunteer's card.

There are $\binom{N}{5}$ possible five-card hands, and $4!\binom{N}{4}$ four-card "messages" (including orderings) that the assistant can send the magician. Thus, we are looking for the largest $N$ such that the number of hands is less than or equal to the number of messages:

$$ \binom{N}{5}\leq 4!\binom{N}{4} $$

solving this inequality yeilds:

$$ N\leq 124 $$

(The answer GentlePurpleRain gave in his comment.) For $N=124$, we have:

$$ \binom{124}{5}=225\,150\,024 $$

possible hands and

$$ 4!\binom{124}{4}=225\,150\,024 $$

possible messages. Since the inequality is saturated, we must devise a one-to-one mapping from hands to messages such that each message is a subset of its corresponding hand. (I'm still working on that part...)