Take a regular deck of 52 cards. Each card has a suit and a value. The suit is one of four possibilities: heart, diamond, club, spade. The value is one of 13 possibilities: A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K. There is exactly one card for each of the 4 x 13 possible combinations of suit and value. Ask your friend to lay the cards out into a grid with 4 rows and 13 columns. They can fill the cards in any way they’d like. In this problem, you will show that you can always pick out 13 cards, one from each column of the grid, so that you wind up with cards of all 13 possible values. (a) Explain how to model this trick as a bipartite matching problem between the 13 column vertices and the 13 value vertices. Can there be vertices in your graph with a degree less than 4? (b) Show that any n columns must contain at least n different values and prove that a matching must exist.
The Correct Answer and Explanation is:
To solve this problem, we’ll model it using bipartite graph matching, a classic approach in combinatorics and graph theory.
(a) Modeling the Trick as a Bipartite Matching Problem
We define a bipartite graph with two sets of vertices:
- Left side (Columns): 13 vertices, one for each column in the grid.
- Right side (Values): 13 vertices, one for each card value (A, 2, …, K).
We draw an edge between a column and a value if that column contains at least one card of that value.
Degree of Vertices
Each column contains 4 cards (since there are 4 rows), and all values are distinct across the deck. Thus, a column can be connected to at most 4 value vertices—so each column vertex has degree at most 4. It’s possible for a column to have less than 4 unique values (if, for instance, two cards in a column had the same value, which is not possible in a standard deck), but since all cards are distinct and no value repeats in a column, each column has 4 distinct values. Therefore, each column vertex has exactly degree 4. On the value side, a value appears once in each of the four suits, so there are 4 cards of each value spread across the 13 columns. Hence, each value vertex has degree 4 as well.
(b) Hall’s Theorem and Existence of Matching
We aim to find a perfect matching: 13 edges connecting each column to a unique value, with no values repeated.
Apply Hall’s Marriage Theorem:
A perfect matching from the column side to the value side exists if and only if for every subset SSS of nnn columns, the union of their value neighbors contains at least nnn distinct values.
Let’s prove this.
Each column has 4 values, so nnn columns have 4n4n4n total card entries. Since all cards are unique, no value can occur more than 4 times in total. To cover 4n4n4n card entries using fewer than nnn values, we’d need some value to appear more than 4 times, contradicting the rule.
Thus, any nnn columns must involve at least nnn distinct values.
So Hall’s condition is satisfied, and a perfect matching exists. That is, you can always pick 13 cards (one per column) with all 13 values represented.
