strategy - Five Card Magic Trick with $N$ card Deck

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

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.