A magic trick - find out the fifth card if four is given Here is a magic trick I saw. My question is how the magician and his partner did it.
Given the simple French deck of cards, with $52$ cards. A person from the audience chooses randomly five cards from the deck and gives it to the partner (the partner works with the magician), without showing it to the magician. Then the partner (who sees the five cards) chooses four cards from the five cards, and gives it to the magician one by one (so the order of the four cards matters). From that the magician knows the fifth card. 
The partner and the magician can’t communicate during the trick. How did they do it?
I thought that amoung the five cards there will be two with the same sign (Spades,Hearts,Diamonds or Clubs) and one of these two cards will be the fifth, and the other will be the first card to give to the magician...
 A: It's a cute one. Let's just assume the cards are numbered $\{1 \dots 52\}$. We draw cards $a_1 < a_2 < a_3 < a_4 < a_5$, and hand out in this order $b_1, b_2, b_3, b_4$. The way we order this set $B={b_1, b_2, b_3, b_4}$ already allows to transmit quite some information. Indeed, choosing the orders paramounts to choosing a permutation on the 4 elements of $B$. There are $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$ such permutations.
This is not enough still to transmit the $5$th which is in a set of size $52$. Well, we also know that the 5th card is different from those $4$ firsts ones: there is only $52-4 = 48$ possibilities. 
I'll leave it to you to complete the strategy. Note that $48/24 = 2$, so we just need to find a trick to only half the search space. Note also that we have still not fixed how we choose the secret card among the set $A$. At last, note at least one of the two inequalities:
 - $a_2 \leq 25$
 - $a_4 \geq 58-25$.
A: There is in fact a solution which uses your idea: that some suit will be repeated twice.
Say that among the $13$ ranks within a suit, ordered $A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K$, each rank "beats" the next six ranks, wrapping around when we get to the end. For example, $A$ beats $2,3,4,5,6,7$, and $10$ beats $J, Q, K, A, 2, 3$.
If you have two cards of the same suit, exactly one of them beats the other one. So you should pass, in order:


*

*A card of the same suit as the missing card, which beats the missing card. This leaves six possibilities for the missing card.

*The remaining three cards, in an order that encodes which of the six possibilities it is.


For the second step, we should order all $52$ cards in the deck somehow; for instance, say that $\clubsuit < \diamondsuit < \heartsuit < \spadesuit$ and $A < 2 < 3 < \dots < Q < K$. Then the order of the last three cards is one of "Low, Middle, High", "Low, High, Middle", and so on through "High, Middle, Low". Just remember some correspondence between these six possibilities and the values $+1, +2, +3, +4, +5, +6$, and add the value you get to the rank of the first card (wrapping around from $K$ to $A$ of the same suit).

For example, say that the correspondence we chose in the second step is
\begin{array}{ccc|c}
\text{Low} & \text{Middle} & \text{High} &+1 \\
\text{Low} & \text{High} & \text{Middle} &+2 \\
\text{Middle} & \text{Low} & \text{High} &+3 \\
\text{Middle} & \text{High} & \text{Low} &+4 \\
\text{High} & \text{Low} & \text{Middle} &+5 \\
\text{High} & \text{Middle} & \text{Low} &+6
\end{array}
and you draw the cards $\{4\clubsuit, 5\spadesuit, 5\diamondsuit, A\clubsuit, J\spadesuit\}$. 


*

*We have two possibilities for the repeated suit, so let's choose $\spadesuit$.

*In the cyclic order in that suit, $5\spadesuit$ beats $J\spadesuit$, so the first card we pass is $5\spadesuit$.

*We want to encode the offset $+6$, which is the ordering High, Middle, Low.

*So we pass that ordering: after $5\spadesuit$ we pass $5\diamondsuit, 4\clubsuit, A\clubsuit$ in that order, because $5\diamondsuit > 4\clubsuit > A\clubsuit$.

A: Let $S$ be a set of all cards.
So we have a set $A$ of all ordered $4$-couples of the set $S$  and a set $B$ of all $5$ subsets of the set $S$.  
Connect 4-couple in $A$ with a subset in $B$ iff all four card from that 4-couple are in that subset. Clearly each 4-couple is connected to $8$ 5-subsets and every 5 subset is connected to $5!= 120$ 4-couples. 
This relation give us a bipartite graph $G=(A,B)$. Now this graph satisfies Hall matching condition. Take any subset $X$ in $B$. Then the set of neighbours $N(X)$ satisfies: $$48 \cdot |N(X)| \geq 120\cdot |X|\implies |N(X)|\geq |X| $$
So there exist a matching which saturate all vertices in $B$.
A: Here is an explicit strategy that works for $n \leq 100$ cards.
As seen in previous answers, we use the order of the 4 transmitted cards to encode a number between 1 and 24. Now if the magician can reduce from the set of the 4 transmitted cards the possible 5th cards to at most 24, we are done.
Mathematically speaking, we want to find a map
$$
f: \mathrm{Comb}_5^n \to \mathrm{Comb}_4^n
$$
that satisfies $c \supseteq f(c)$ for all $c \in \mathrm{Comb}_5^n$ and $|f^{-1}(c)| \leq 24$ for all $c \in \mathrm{Comb}_4^n$. Here $\mathrm{Comb}_k^n$ denotes all the subsets of $\{1,...,n\}$ of size 5.
My proposed map $f$ is given as follows: WLOG the cards are numbered from 1 to $n$. For $c \in \mathrm{Comb}_5^n$ take the sum of the card numbers modulo 5, call this $1 \leq d \leq 5$, and remove the $d$th smallest card.
This works as long as $n \leq 100$: Given $c \in \mathrm{Comb}_4^n$, what is $f^{-1}(c)$ ? Go through the cards 1,2,3,...,$n$, assume this is the removed card, each time compute the respective $d$, and check whether this $d$ would have actually led to remove this card. One quickly sees that this is the case for roughly every 5th card, maybe slightly more. If you think it through this goes for at most $\lceil n/5 \rceil + 4$, which must be $\leq 24$, leaving us with $n \leq 100$.
(If you look at the details, e.g. that one can also exclude the 4 cards given, this works actually for slightly bigger $n$ as well.)
It's not thaat practical on a real table, but certainly doable!
