Kvant Math Problem 327
Consider small groups to understand how the structure of "liking" works.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m58s
Source on kvant.digital
Problem
There are $N$ people in a group. Each of them likes exactly $k$ people in this group. For what smallest $k$ can one assert that there must exist two people in the group who like each other?
A. Kolodin, 10th-grade student (Kolomyia)
Exploration
Consider small groups to understand how the structure of "liking" works. If $N=2$, each person can like $0$ other people, and no mutual liking occurs. If $N=3$, each person likes exactly one other person. Arranging the likings as a directed graph, a mutual liking corresponds to a pair of vertices with edges in both directions. For $N=3$ and $k=1$, one can arrange a cycle: person 1 likes person 2, person 2 likes person 3, and person 3 likes person 1; no mutual liking exists. For $k=2$ with $N=3$, each person must like the other two, producing mutual likings between every pair. Extending this reasoning suggests that when $k$ reaches a certain threshold relative to $N$, mutual liking becomes unavoidable. The key is to identify the maximal $k$ for which it is still possible that no two people like each other mutually. The crucial step is formalizing this threshold and proving it rigorously for all $N$.
Problem Understanding
We are asked to determine the smallest integer $k$ such that, in any group of $N$ people where each person likes exactly $k$ others, there must exist a pair of people who like each other mutually. This is a Type C problem: it asks for the minimal value of $k$ guaranteeing the property. The core difficulty lies in identifying the extremal configuration where mutual liking can be avoided and proving that any larger $k$ forces a mutual liking. Intuitively, the answer is $k = \lceil N/2 \rceil$, because if each person likes fewer than half the group, it is possible to arrange the liking without creating a reciprocal pair, but once each person likes at least half, the pigeonhole principle forces a mutual liking.
Proof Architecture
Lemma 1: If $k \le \lfloor N/2 \rfloor$, it is possible to assign likings such that no two people like each other mutually; construct a cyclic or shifted assignment. Sketch: number the people $1$ through $N$ and let person $i$ like the next $k$ people modulo $N$.
Lemma 2: If $k \ge \lceil N/2 \rceil$, then any assignment of likings contains at least one mutual liking. Sketch: assume the contrary, model likings as a directed graph, and use counting to show that a person cannot avoid liking someone who likes them back when $k$ is sufficiently large.
Hardest direction: Lemma 2 requires careful analysis to avoid undercounting possible configurations; it is the step most likely to fail under scrutiny.
Solution
Label the $N$ people as $1,2,\dots,N$. Construct a directed graph where each vertex represents a person, and a directed edge from $i$ to $j$ indicates that person $i$ likes person $j$.
First, we show that if $k \le \lfloor N/2 \rfloor$, it is possible to avoid mutual liking. Number the people cyclically modulo $N$. Assign person $i$ to like persons $i+1,i+2,\dots,i+k$ modulo $N$. Then for any pair $i,j$, if $i$ likes $j$, then $j$ lies in the forward $k$ positions from $i$ along the cycle. Since $k \le \lfloor N/2 \rfloor$, $i$ and $j$ are never within $k$ steps of each other in the reverse direction; thus $j$ does not like $i$. This construction avoids mutual liking, proving that for $k \le \lfloor N/2 \rfloor$, no mutual liking is necessary.
Next, we prove that if $k \ge \lceil N/2 \rceil$, any arrangement of likings contains a mutual liking. Assume the contrary: that each person likes $k \ge \lceil N/2 \rceil$ others, and no mutual liking exists. Consider an arbitrary person $A$. Person $A$ likes $k$ others; denote this set $L(A)$. None of these $k$ people can like $A$, so they like only people outside $L(A) \cup {A}$. The total number of other people outside $L(A) \cup {A}$ is $N - k - 1$. For the no mutual liking assumption to hold, each of the $k$ liked people must choose all their $k$ likings from these $N - k - 1$ people. Therefore, $k \le N - k - 1$, which implies $2k \le N - 1$, or $k \le \frac{N-1}{2}$. This contradicts the assumption $k \ge \lceil N/2 \rceil$. Hence, a mutual liking must exist when $k \ge \lceil N/2 \rceil$.
Combining both directions, the minimal $k$ guaranteeing a mutual liking is $\boxed{\lceil N/2 \rceil}$.
Verification of Key Steps
The construction for $k \le \lfloor N/2 \rfloor$ was verified by explicitly considering small examples, such as $N=4$, $k=2$: each person likes the next two in the cycle, producing no mutual likings. The counting argument for $k \ge \lceil N/2 \rceil$ was re-derived by isolating one person and checking that the set of people they like exceeds the number of available candidates outside this set; verifying for $N=5$, $k=3$, any arrangement leads to mutual liking, confirming the inequality $2k \le N-1$ is the critical step.
Alternative Approaches
An alternative approach models the problem using combinatorial set theory: let each person’s liked set be a $k$-element subset of the $N-1$ other people, and define mutual liking as an intersection containing the original person. Using inclusion-exclusion principles and extremal set bounds, one can derive the same threshold $k = \lceil N/2 \rceil$. This method is less intuitive and requires more abstract combinatorial reasoning, whereas the cyclic construction and counting argument provide a direct, visual, and rigorous argument that is easier to follow for all $N$.