|
|
dmoi Example 4.6.2.
| Suppose you deal 52 regular playing cards into 13 piles of 4 cards each. Prove that you can always select one card from each pile to get one of each of the 13 card values Ace, 2, 3, …, 10, Jack, Queen, and King. |
Solution.
Doing this directly would be difficult, but we can use the matching condition to help. Construct a graph $G$ with 13 vertices in the set $A$, each representing one of the 13 card values, and 13 vertices in the set $B$, each representing one of the 13 piles. Draw an edge between a vertex $a∈A$ to a vertex $b∈B$ if a card with value $a$ is in the pile $b$. Notice that we are just looking for a matching of $A$; each value needs to be found in the piles exactly once.
We will have a matching if the matching condition holds. Given any set of card values (a set $S⊆A$) we must show that $|N(S)|≥|S|$.
That is, the number of piles that contain those values is at least the number of different values. But what if it wasn't? Say $|S|=k$.
If $|N(S)|<k$, then we would have fewer than $4k$ different cards in those piles (since each pile contains 4 cards). But there are $4
k$ cards with the $k$ different values, so at least one of these cards must be in another pile, a contradiction. Thus the matching condition holds, so there is a matching, as required. |
|
