Kvant Math Problem 835

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m31s
Source on kvant.digital

Problem

In a single-round chess tournament, $n$ players from country $A$ and $n$ players from country $B$ participated. It turned out that no matter how the players were paired (so that players from different countries played against each other), there is always at least one pair of players who have already faced each other before. Prove that it is possible to select $a$ players from country $A$ and $b$ players from country $B$ such that each of the selected $a$ players has played against each of the selected $b$ players, and $a+b\gt n$.

L. D. Meniches

Exploration

Represent the previous encounters by a bipartite graph. Let the vertices on the left be the $n$ players from country $A$, the vertices on the right be the $n$ players from country $B$, and join $A_i$ to $B_j$ when those two players have already played each other before the tournament.

The hypothesis says that for every pairing of the players, consisting of $n$ disjoint pairs $A_iB_{\sigma(i)}$, at least one matched edge is present in the graph. Equivalently, there is no perfect matching in the bipartite complement graph $\overline G$, where an edge means that the two players have not met before.

The desired conclusion asks for subsets $X\subseteq A$ and $Y\subseteq B$ such that every vertex of $X$ is adjacent in $G$ to every vertex of $Y$, and $|X|+|Y|>n$. In graph language, we must find a complete bipartite subgraph $K_{a,b}$ in $G$ with $a+b>n$.

Since the complement graph $\overline G$ has no perfect matching, Hall's theorem immediately comes to mind. Applying Hall to $\overline G$, there exists a subset $S$ of the $A$-side with $|N_{\overline G}(S)|<|S|$.

Let $T=N_{\overline G}(S)$. Every vertex of $S$ is connected in $\overline G$ only to vertices of $T$. Hence in the original graph $G$, every vertex of $S$ is adjacent to every vertex of $B\setminus T$. Thus $S$ and $B\setminus T$ form a complete bipartite subgraph of $G$.

Its size parameter is

$$|S|+|B\setminus T| = |S|+n-|T|.$$

Since $|T|<|S|$, this quantity exceeds $n$.

The crucial point is verifying carefully that Hall's theorem is applied to the complement graph and that the complete bipartite subgraph in $G$ is exactly $S\times(B\setminus T)$.

Problem Understanding

We have $n$ players from country $A$ and $n$ players from country $B$. Before the tournament, some pairs consisting of one player from each country may already have played each other.

No matter how one chooses a pairing between the two countries for the tournament, at least one paired couple has already met before. We must prove that there exist $a$ players from country $A$ and $b$ players from country $B$ such that every selected player from country $A$ has previously played every selected player from country $B$, and

$$a+b>n.$$

This is a Type B problem. The main difficulty is translating the condition about all possible pairings into a structural statement about a bipartite graph and then extracting a large complete bipartite subgraph.

Proof Architecture

Consider the bipartite graph $\overline G$ whose edges join pairs of players from different countries that have never previously played each other; the hypothesis is equivalent to saying that $\overline G$ has no perfect matching.

By Hall's theorem, if a bipartite graph with equal part sizes has no perfect matching, then there exists a subset $S$ of one side such that $|N_{\overline G}(S)|<|S|$.

Let $T=N_{\overline G}(S)$. Every vertex of $S$ has no neighbors in $\overline G$ outside $T$, hence every vertex of $S$ is connected in the original graph $G$ to every vertex of $B\setminus T$.

The sets $S$ and $B\setminus T$ therefore span a complete bipartite graph in $G$.

Since $|T|<|S|$, we obtain

$$|S|+|B\setminus T| = |S|+n-|T| > n.$$

The lemma most likely to fail under scrutiny is the passage from $T=N_{\overline G}(S)$ to the statement that $S$ is completely joined to $B\setminus T$ in the original graph. This must be checked directly from the definition of the complement graph.

Solution

Let $G$ be the bipartite graph whose left part consists of the $n$ players from country $A$ and whose right part consists of the $n$ players from country $B$. Two vertices are joined in $G$ if and only if the corresponding players had already played each other before the tournament.

Let $\overline G$ be the bipartite complement of $G$. Thus an edge of $\overline G$ joins a player from country $A$ to a player from country $B$ precisely when those two players have not previously met.

A pairing of the tournament is exactly a perfect matching between the $A$-players and the $B$-players. The hypothesis states that every such pairing contains at least one pair of players who have already met. In terms of $\overline G$, this means that no perfect matching of all $n$ pairs can be formed using only edges of $\overline G$.

Hence $\overline G$ has no perfect matching.

Since the two parts of $\overline G$ both have size $n$, Hall's theorem implies that there exists a subset $S$ of the $A$-part such that

$$|N_{\overline G}(S)|<|S|,$$

where $N_{\overline G}(S)$ denotes the set of neighbors of $S$ in $\overline G$.

Put

$$T=N_{\overline G}(S).$$

Take any vertex $x\in S$ and any vertex $y\in B\setminus T$. Because $y\notin T$, the vertex $y$ is not adjacent in $\overline G$ to any vertex of $S$. In particular, $x$ and $y$ are not adjacent in $\overline G$.

By the definition of the complement graph, this means that $x$ and $y$ are adjacent in $G$. Since $x\in S$ and $y\in B\setminus T$ were arbitrary, every vertex of $S$ is adjacent in $G$ to every vertex of $B\setminus T$.

Therefore the sets

$$S\subseteq A, \qquad B\setminus T\subseteq B$$

span a complete bipartite subgraph of $G$.

Let

$$a=|S|, \qquad b=|B\setminus T|.$$

Then

$$a+b = |S|+n-|T|.$$

Because $|T|<|S|$,

$$a+b = |S|+n-|T| > n.$$

Thus we have found $a$ players from country $A$ and $b$ players from country $B$ such that every selected player from country $A$ has already played every selected player from country $B$, and

$$a+b>n.$$

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the translation of the hypothesis. A perfect matching in $\overline G$ corresponds to a pairing in which every paired couple has never met before. The hypothesis asserts that every pairing contains at least one previously played encounter. Consequently such a perfect matching cannot exist. The equivalence is exact because every pairing between the two countries is a perfect matching of the bipartite vertex classes.

The second delicate step is proving that $S$ and $B\setminus T$ form a complete bipartite graph in $G$. Since $T=N_{\overline G}(S)$, every neighbor in $\overline G$ of every vertex of $S$ lies inside $T$. Hence no edge of $\overline G$ joins a vertex of $S$ to a vertex of $B\setminus T$. The bipartite complement relation then forces all such pairs to be edges of $G$.

The final inequality requires only the strict Hall deficiency:

$$|T|<|S|.$$

Substituting into

$$|S|+n-|T|$$

gives a quantity strictly larger than $n$. If one had only $|T|\le |S|$, the conclusion would yield merely $a+b\ge n$, which is insufficient. The strict inequality furnished by Hall's criterion for failure of a perfect matching is exactly what is needed.

Alternative Approaches

The proof can be phrased entirely in terms of marriage problems. Let an edge represent a pair of players who have never met. The assumption says that it is impossible to arrange marriages between all players of country $A$ and all players of country $B$ using only such edges. Hall's theorem then produces a set $S$ of players from country $A$ whose pool of possible partners is too small. The players of country $B$ outside that pool have already met every member of $S$, yielding the required complete bipartite configuration.

Another route is to use the König-Egerváry theorem. Since the complement graph has no perfect matching, its maximum matching has size at most $n-1$. König's theorem gives a vertex cover of size at most $n-1$. The complements of the covered vertices on the two sides form a complete bipartite subgraph in the original graph, and the count of uncovered vertices exceeds $n$. This approach is slightly more indirect because it invokes the matching-cover duality, whereas the Hall argument produces the required subsets immediately.