- #1
TheMathNoob
- 189
- 4
Homework Statement
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). M
Homework Equations
Halls theorem IN(A)l>= A
If this is true for every subset of A then the bipartite graph has a complete matching
The Attempt at a Solution
It's too easy. I think. We are going to have a set A which contains the suits and a set B which contains the piles.
Set A={A,2,3,4,5,6,7,8,9,10,j,q,k}
Set B={13 piles}
The trick to prove this is to know that every element in the set A will always have 4 lines going out no matter where, so lN(A)l >=A because no matter which subset of the set A we pick, every vertex in the set A will always have 4 neighbors and intuitively the addition of those neighbors will be always greater that the number of vertices or elements in A
As easy as that?