Kvant Math Problem 428
The problem is naturally translated into graph theory.
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m43s
Source on kvant.digital
Problem
In an olympiad there are $(m-1)n+1$ participants. Prove that among them either there exist $m$ participants who are pairwise unacquainted with each other, or there exists a participant who is acquainted with at least $n$ participants of the olympiad. Does the statement remain true if the number of participants in the olympiad is reduced by one?
E. Turkevich
Exploration
The problem is naturally translated into graph theory. Each participant is a vertex of a simple undirected graph, where an edge represents acquaintance. The condition “pairwise unacquainted” becomes an independent set in this graph, while “a participant acquainted with at least $n$ others” becomes a vertex of degree at least $n$.
Thus the statement becomes: for a graph with $(m-1)n+1$ vertices, either there is an independent set of size $m$, or there is a vertex of degree at least $n$.
The natural strategy is to assume that all degrees are at most $n-1$ and deduce the existence of a large independent set. A greedy construction suggests itself: repeatedly choose a vertex, discard it together with all its neighbors, and repeat. The key point is that each step removes at most $n$ vertices.
The sharpness question suggests looking for a graph on $(m-1)n$ vertices with maximum degree at most $n-1$ and independence number at most $m-1$. A disjoint union of $m-1$ cliques of size $n$ appears to match these constraints exactly.
Problem Understanding
This is a Type A problem. One must prove a dichotomy: either there exists a vertex of degree at least $n$, or there exists an independent set of size $m$. Then one must determine whether the statement remains valid after reducing the number of vertices by one.
The core difficulty is to convert a local degree restriction into a global lower bound on the independence number via a clean extremal argument.
The statement is true for $(m-1)n+1$ vertices, and false for $(m-1)n$ vertices.
Proof Architecture
One considers a graph $G$ with $(m-1)n+1$ vertices and assumes that every vertex has degree at most $n-1$. Under this assumption, one constructs an independent set iteratively by repeatedly selecting a vertex and deleting it together with all its neighbors.
The key lemma is that each deletion removes at most $n$ vertices, ensuring a lower bound on the number of selected vertices.
The hardest step is the justification that the greedy selection always produces an independent set and that the counting argument guarantees at least $m$ vertices.
To disprove the reduced statement, one constructs a disjoint union of $m-1$ cliques of size $n$ and verifies both constraints.
Solution
Let $G$ be a graph whose vertices represent participants, and where an edge connects two acquainted participants. An independent set in $G$ is a set of pairwise unacquainted participants.
Assume first that $G$ has $(m-1)n+1$ vertices and that every vertex has degree at most $n-1$. We construct a set $S$ iteratively. Initially $S$ is empty and all vertices are unmarked. While vertices remain, choose any remaining vertex $v$, add it to $S$, and delete $v$ together with all vertices adjacent to $v$.
Each step removes $v$ and all its neighbors. Since $\deg(v)\le n-1$, each step removes at most $n$ vertices.
No two vertices added to $S$ can be adjacent, since whenever a vertex is chosen, all its neighbors are deleted immediately. Hence $S$ is an independent set.
Let $k$ be the number of selected vertices. Each selection removes at most $n$ vertices, so at most $kn$ vertices are removed in total. Since the graph initially has $(m-1)n+1$ vertices, after $m-1$ selections at most $(m-1)n$ vertices would be removed, leaving at least one vertex unremoved. Therefore a further selection is possible, so the process continues until at least $m$ vertices are chosen. Hence $|S|\ge m$.
Thus, if no vertex has degree at least $n$, then there exists an independent set of size at least $m$. This proves the first statement.
Now consider $(m-1)n$ vertices. Construct a graph consisting of $m-1$ disjoint complete graphs, each on $n$ vertices. In each clique every vertex has degree $n-1$, so no vertex has degree at least $n$. Any independent set can contain at most one vertex from each clique, since all vertices inside a clique are pairwise adjacent. Hence the largest independent set has size $m-1$, and no independent set of size $m$ exists.
This shows that the statement fails when the number of participants is reduced by one.
Therefore the original bound $(m-1)n+1$ is sharp. ∎
Verification of Key Steps
The greedy construction relies on the fact that after selecting a vertex $v$, all vertices removed are exactly $v$ together with its neighbors, so no later chosen vertex can be adjacent to any earlier one. This guarantees independence without additional argument.
The counting argument hinges on the bound that each step removes at most $n$ vertices. If $k$ vertices are selected, at most $kn$ vertices are removed, so with $(m-1)n+1$ initial vertices, $k\ge m$ is forced; otherwise $(m-1)n+1$ would not be fully exhausted after only $m-1$ steps.
In the extremal construction, the degree condition is tight since every vertex lies in a clique of size $n$ and hence has degree exactly $n-1$, while independence is limited because any two vertices in the same clique are adjacent, forcing at most one choice per component.
Alternative Approaches
An alternative proof uses the complement graph and the observation that the statement becomes a bound relating clique number and minimum degree in the complement. One can also derive the result via a direct induction on $m$, removing a vertex of maximum degree and analyzing the remaining graph.
The greedy deletion argument is preferable because it directly produces the independent set and yields a transparent extremal bound without auxiliary induction or dual reformulation.