Show that the following magic trick is possible.
Two magicians call three spectators and have them sit on three chairs. One magician (call them B), goes out of the room. The other magician (A) spreads out 27 cards in front of the spectators, and each is asked to take a card of their choice.
Once the spectators choose, A points to a card from the remaining 24 and has the spectators add it to their set of three cards (i.e. A does not touch that card). The spectators are allowed to shuffle the four cards. B is then called back and one of the spectators hands B the four shuffled cards. Looking at the 4 cards, B now announces which spectator chose which card.
.
.
.
.
.
Solution:
Lets label the chairs (and hence the spectators) 1,2,3. The magicians agree upon this before hand.
There are $6 \binom{27}{3} =17550$ possibilities for spectators cards. The number of possibilities for the 4 cards handed to B is $\binom{27}{4} = 17550$. Thus we need to find a pairing for each possibility of the spectator's pick to a 4 element superset.
Now look at this as a bipartite graph.
One vertex set is the set of spectator possibilities (call it $S$) and the other is the set of 4 elements subsets (call if $F$).
Each spectator possibility $s \in S$ has exactly 24 neighbours in $F$. Each 4 element set $f \in F$ has exactly $6\binom{4}{3} = 24$ neighbours in the spectator set $S$.
This is a regular bi-partite graph and by a simple application of Hall's theorem, has a perfect matching.
A brief sketch is:
If $L$ is a subset of $S$ and $N(L) \subset F$ is the set of neighbours of $L$, then the number of edges in the induced subgraph of $G(L, N(L))$ is $24|L|$. Since the degree of each vertex of $F$ is 24, the degree of the $F$ vertices in $G(L, N(L))$ is at most $24$. Thus we must have that $24 |N(L)| \ge 24 |L|$ and thus $|N(L)| \ge |L|$, satisfying the condition of hall's theorem.
