3
$\begingroup$

I am reading the Wikipedia article entitled Hall's marriage theorem. It states we can use the theorem to prove the following:

"Take a standard deck of cards, and deal them out into 13 piles of 4 cards each. Then, using the marriage theorem, we can show that it is always possible to select exactly 1 card from each pile, such that the 13 selected cards contain exactly one card of each rank (Ace, 2, 3, ..., Queen, King)."

The article doesn't say HOW Hall's theorem can be used to prove this.

I think we could create a bipartite graph with one partite set consisting of each of the 13 ranks and the other partite set consisting of the 13 piles. An edge joins a rank to a pile if that rank is in the pile. Each rank would be joined to at least one pile and at most 4 piles. This is as far as I have gotten.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Take any subset of ranks, call it $A$. Because there are 4 cards for each rank, it has at least $4|A|$ connections, thus it has to connect to at least $4|A|/4=|A|$ card piles. Hence $|N(A)| \geq |A|$. $\endgroup$ – dtldarek Aug 5 '16 at 16:27
  • $\begingroup$ I do not agree that A has at least 4 |A| connections. It could have as few as |A|. Right? $\endgroup$ – Geoffrey Critzer Aug 5 '16 at 16:46
  • 1
    $\begingroup$ By connections I mean edges in a multigraph. That means $A$ has at least $|A|$ neighbors in the multigraph, but then if you merge multiple repated edges into a single one to obtain a normal graph, the number of neighbors doesn't change. $\endgroup$ – dtldarek Aug 6 '16 at 8:00
  • $\begingroup$ OK! Thank you. I agree. $\endgroup$ – Geoffrey Critzer Aug 6 '16 at 12:09
3
$\begingroup$

You are exactly right, create a bipartite graph, with $13$ vertices in each side, on one side you have the $13$ piles and on the other the $13$ ranks. Connect a pile with a rank if and only if the pile contains the rank.

If we can find a perfect matching we would be done, because for each pile you select one card with the rank to which the pile is connected, and no two selected cards will have the same rank.

We must only prove that this graph has a perfect matching, we use Hall's theorem.

Select any subset of ranks, say they are $k$, we must prove that there are at least $k$ piles that contain at least one card from one of the ranks. Suppose not, then we can find $k-1$ piles that contain all of the cards from the $k$ ranks, impossible, since there are $4k$ cards from the selected ranks, and those piles would have $4(k-1)$ cards.

Improve this answer
$\endgroup$
  • $\begingroup$ Yes! Thank you. It seems very simple now. I think what hindered my thinking is that I do not understand the sufficiency part of the proof of Hall's theorem. But at least I see now how it applies to this problem. $\endgroup$ – Geoffrey Critzer Aug 5 '16 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.