Skip to content

5.28 Matching

  1. A \(8 \times 8\) table has exactly 3 letters A and 5 letters B in each row and each column. Show that one can exchange eight A to C such that no two C are in the same row or column.

    image​

    every row has exactly one \(C\) ensure that the degree of \(v\in V_0\) are all one. The same as column

    The way of changing A's to C's corresponds to a matching on this graph.

    image​

    Pick \(S \subset \{a,b,c,d,e,f,g,h\}\). NTP \(\#S \le \#N(S)\).

    image​

    #Edges outgoing from elements of \(S\) is \(3\#S\). All these edges connect the vertices of \(S\) to vertices of \(N(S)\)

    Consider all the edges outgoing from the vertices of \(N(S)\). There are \(3\#N(S)\) such edges.

    (Edges from \(S\)) \(\subset\) (Edges from \(N(S)\)), then \(3\#S \le 3\#N(S) \Rightarrow \#S \le \#N(S)\)​

    Remark: For any \(k\)-regular(degree of vertex is k) bipartite graph, Hall's condition holds.

  2. A unit square is partitioned into n polygons of equal area in two different ways. Show that one can choose n points in the square such that every polygon of any partition contains a point.

    image​

    Every polygon of partition 1 and every polygon of partition 2 have exactly one puncture.

    Edge = non-zero area intersection: image​

    Hall's condition:
    pick \(S = \{1, ..., n\}\)
    How do we describe \(N(S)\)? = All the parts of the second partition that intersect at least one element of \(S\) with a non-zero intersection area.

    Total area of elements of \(S \le\) total area of the elements of \(N(S)\).

    Use that all part have the same area: \(\frac{1}{n}\#S\le \frac{1}{n}\#N(S)\)

    image​

  3. A spectator writes a sequence of n decimal digits on the whiteboard. The assistant of the magician covers some three of the written digits by cards of three different colors. The magician is supposed to guess what digits are missing and the order of the missing digits. What is the minimal n this trick is possible in principle.

    image​

    image​

    And the number of \(V_0\) should less than \(V_1\), otherwise, the magician cannot guess

    Assistant can see \(10^n\) diff. sequences. Configuration: \(n(n-1)(n-2) \cdot 10^{n-3}\)

    Inequality: \(10^3 \leq n(n-1)(n-2) \Rightarrow n\) is at least 12.

    To prove that it is possible for \(n=12\). NEED to check Hall's condition.

‍