Skip to content

Homework 10

  1. A 52-card deck is dealt into 13 rows of 4 cards each. Prove that you can always select one card from each row such that you get exactly one card of each rank.

    imageimage​

    \(v \in V_0\) connect to \(u \in V_1\) if u's type is same with \(v\)

    A saturating matching is one arrangement method of one card of each rank.
    Pick \(S \subseteq \{A, 2, 3, \ldots, J, Q, K\}\). NTP \(\#S \leq \#N(S)\).
    And \(N(S)\) is the rows that have the same type cards with \(S\).
    We know there are four edges outgoing from each \(v \in S\) and at most 4 edges outgoing from each \(v \in N(S)\). And we know (Edges from \(S\)) \(\subseteq\) (Edges from \(N(S)\)).
    Thus \(4\#S \leq (\text{Edges from } N(S)) \leq 4\#N(S)\). Thus \(\#S \leq \#N(S)\).
    Thus Hall's condition holds, thus there is a such saturating matching.
    Thus, you can always select one card from each row such that you get exactly one card of each rank.

  2. A round-robin tournament of \(2n\) teams lasted for \(2n-1\) days, as follows. On each day, every team played one game against another team, with one team winning and one team losing in each of the \(n\) games. Over the course of the tournament, each team played every other team exactly once. Can one necessarily choose one winning team from each day without choosing any team more than once.

    image​

    Let \(V_0 = \{Day_1, Day_2, \dots, Day_{2n-1}\}\), \(V_{1} = \{Team_{1}, Team_{2}, \dots, Team_{2n}\}\)

    \(D_i\) connect \(T_j\) if in \(Day_i\), Team \(j\) wins.

    Then a saturating matching is a way of choosing one winning team from each day without choosing any team more than once.

    Pick \(S \subseteq \{D_1, \dots, D_{2n-1}\}\), \(N(S)\) is the winner in these days.
    We know there are \(n\) edges outgoing from each \(v \in S\) since there are \(n\) games per day, and \(n\) winners per day.
    And each team can win at most \(\#S\) times.
    And (Edges from \(S\)) \(\subset\) (Edges from \(N(S)\)), then \(\#S \cdot n \leq\) Edges from \(N(S) \leq \#S \#N(S)\).
    Then \(n \leq \#N(S)\).
    If \(\#S \leq n\), then \(\#S \leq \#N(S)\). We are done
    If \(\#S > n\), NTP \(\#N(S) \geq \#(S)\).

    If \(\#N(S)=2n\), then we know \(\#(S)\leq 2n-1\), thus \(\#N(S) \geq \#(S)\)

    If \(\#N(S)\leq 2n-1\), then \(\exists T_j\) lose all games in \(\#(S)\). Thus \(T_j\) have played with \(\#(S)\) distinct teams, then there are greater or equal than \(\#(S)\) teams win the games. Then \(\#N(S)\geq \#(S)\)
    Thus there is a saturating matching always.
    Thus we can choose one winning team from each day without choosing any team more than once.

  3. A permutation matrix \(P\) is a square matrix such that every its row and every its column contain exactly one 1, and all the other entries are 0. For example: \(P = \begin{pmatrix}0 & 1 & 0 \\0 & 0 & 1 \\1 & 0 & 0\end{pmatrix}.\)
    Prove that if \(M\) is an \(n \times n\) matrix, where its entries \(m_{ij}\) are non-negative integers that satisfy \(\sum_{i=1}^n a_{ij} = \sum_{j=1}^n a_{ij} = k \in \mathbb{N},\) then there exist \(k\) permutation matrices \(p_1, \dots, p_k\) such that
    ​\(M = p_1 + \dots + p_k.\)
    Hint: use induction on \(k\).

    Base case: when \(k=1\), \(M=P\) which is a permutation matrix.
    Suppose it's true for \(k=1\), then for \(k\).
    NTP \(M=P_1 + \dots + P_k + P'\), \(P'\) is a permutation matrix.
    We know there exist \(k\) permutation matrices \(P_{1}, \dots, P_{k}\) s.t. \(P_1 + \dots + P_{k-1} = M'\).
    NTP \(M=M'+P'\) where \(M\) is \(k\), \(M'\) is \(k-1\).
    Let \(V_0\) be the row index and \(V_1\) be the column index for \(M = \begin{pmatrix} a_{11} & \dots & a_{1n} \\ a_{12} & & \\ \vdots & \ddots & \\ a_{1n} & & a_{nn} \end{pmatrix}\).
    ​\(r_i \in V_0\) connect to \(c_j \in V_1\) \(t\) times if \(a_{ij}=t\).

    image​

    We know there are \(k\) edges outgoing \(v \in S\) and \(k\) edges outgoing \(v \in N(S)\).
    And a saturating matching is a permutation matrix \(P'\) we needed

    Since edges \((\text{Edges from } S) \subset (\text{Edges from } N(S))\), then \(k \#S \leq k \#N(S) \Rightarrow \#S \leq \#N(S)\).

    Thus, there is always a saturating matrix. That is, there is always a permutation matrix \(P'\) such that \(M=M'+P'\) and we know \(M'=P_1+\dots+P_{k-1}\).

    Thus \(M=P_1+\dots+P_{k-1}+P'\) with all permutation matrices.

‍