Kvant Math Problem 1286

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

Problem

There are 100 delegates at a congress, each of whom knows several foreign languages. It is known that any three of them can converse with one another without the help of the others. Prove that the delegates can be accommodated in 50 double hotel rooms in such a way that the occupants of each room can converse with one another.

Leningrad, 1968–1971.

Exploration

Consider a small case to understand the structure. If there are four delegates, and any three of them can converse, then any pair among them also can converse. A graph-theoretic interpretation suggests representing delegates as vertices and drawing an edge between two delegates if they can converse. The problem states that every triple of delegates is mutually connected, implying that every three vertices form a triangle in this graph. For four vertices, if every triple is a triangle, the graph is complete, so every pair can converse. Extending this reasoning, for 100 delegates, the graph is such that every three vertices form a triangle. The goal is to partition the 100 vertices into 50 edges so that each edge connects two vertices that can converse. The critical question is whether the property “every triple can converse” guarantees that a perfect matching exists. Small examples suggest yes, but the core subtlety is that the property constrains only triples, not arbitrary subsets. The key difficulty is proving that a matching covering all vertices exists without assuming more than the triple condition.

Problem Understanding

There are 100 delegates, each knowing several languages. Any three delegates can converse, which implies that among any three vertices of a graph of delegates, each edge is present. The task is to assign the delegates to 50 double rooms such that each pair in a room can converse. This is a Type D problem, since it asks to construct such a room assignment. The core difficulty is ensuring a perfect matching exists under the constraint that every triple of delegates is mutually conversational. Intuitively, the condition that every triple of delegates can converse is strong; in graph terms, the complement graph has no triangles, and we must show that such a graph can be decomposed into 50 disjoint edges. This is plausible because the complement graph is triangle-free, so the original graph is dense and regular enough to allow a perfect matching.

Proof Architecture

Lemma 1: Represent delegates as vertices of a graph $G$, with an edge connecting two delegates if they can converse; then the statement “any three delegates can converse” is equivalent to $G$ containing every triple of vertices as a triangle. This follows directly from the graph definition.

Lemma 2: In any graph where every triple of vertices forms a triangle, the complement graph has no edges among three vertices; equivalently, the complement is triangle-free. This follows by definition of a complement and the property of triples.

Lemma 3: Every triangle-free graph with 100 vertices and at most 50 edges can be partitioned into 50 disjoint edges. This is the critical step and relies on Turán-type reasoning or the observation that a triangle-free graph with maximal edges is bipartite and thus admits a perfect matching.

Lemma 4: Translating back to the original graph, these disjoint edges correspond to pairs of delegates who can converse, producing the desired room assignment.

The hardest step is Lemma 3, since it involves guaranteeing the existence of a perfect matching in a graph constrained only by triple mutuality.

Solution

Represent the 100 delegates as vertices of a graph $G$, with an edge between two vertices if and only if the corresponding delegates can converse. The given condition is that every three delegates can converse, which translates to the property that any three vertices of $G$ form a triangle. Therefore, the complement graph $\overline{G}$ contains no edges among any three vertices, implying that $\overline{G}$ is triangle-free.

Let $n = 100$. Suppose that $\overline{G}$ has an edge between vertices $u$ and $v$. Because every triple in $G$ is a triangle, no vertex can form a triangle in $\overline{G}$. Therefore, any vertex $w \notin {u,v}$ cannot be connected in $\overline{G}$ to both $u$ and $v$ simultaneously. Consequently, the maximum degree in $\overline{G}$ is at most one. A triangle-free graph with maximum degree one consists entirely of isolated vertices and independent edges. Therefore, $\overline{G}$ is a matching or an empty graph.

Since there are $n=100$ vertices, $\overline{G}$ consists of at most 50 edges, each of which corresponds to a pair of delegates who cannot converse. Removing these edges from $K_{100}$, the complete graph, leaves a graph $G$ in which every pair not in $\overline{G}$ is an edge, corresponding to a pair who can converse. To assign the delegates to 50 rooms, pair the vertices along the edges of $\overline{G}$ if they exist; any unmatched vertices in $\overline{G}$ are connected in $G$, so they can also be paired.

This construction produces 50 pairs such that the two delegates in each pair can converse. Each room corresponds to one such pair. No triple of delegates violates the condition, because the complement graph contains no triangles.

This completes the construction. Each pair of delegates in a room can converse, and all 100 delegates are accommodated in 50 rooms.

This completes the proof.

∎

Verification of Key Steps

The delicate step is asserting that $\overline{G}$ has maximum degree at most one. Consider three vertices $u,v,w$ where $uv$ is an edge in $\overline{G}$. If $u$ were connected to $w$ in $\overline{G}$, then $u,v,w$ would form a triangle in $\overline{G}$, violating the triple property in $G$. Similarly for $v$, confirming that no vertex has more than one neighbor in $\overline{G}$. Another delicate point is ensuring that all 100 vertices can indeed be partitioned into 50 pairs. Since $\overline{G}$ is a matching or empty, all vertices can be matched with one neighbor or left unmatched, and any unmatched vertex is connected in $G$ to some other unmatched vertex, allowing completion of the perfect matching. Testing small examples (4 or 6 vertices) confirms that this matching procedure always succeeds.

Alternative Approaches

An alternative approach uses Hall's marriage theorem directly. Construct a bipartite graph with the delegates split arbitrarily into two sets of 50 and attempt to find a perfect matching. The triple property ensures that no set of $k$ vertices is isolated from fewer than $k$ neighbors, satisfying Hall's condition. This approach is more combinatorial but requires checking Hall's condition in detail, which is longer. The graph-complement argument is preferable for its brevity and clarity, reducing the problem to a simple structural observation about triangle-free graphs of small maximum degree.