Kvant Math Problem 1395
Consider a small social network where each person has a certain number of acquaintances.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m00s
Source on kvant.digital
Problem
Let us call a person unsociable if they have fewer than 10 acquaintances. Let us call a person an eccentric if all of their acquaintances are unsociable. Prove that the number of eccentrics does not exceed the number of unsociable people.
F. L. Nazarov
Exploration
Consider a small social network where each person has a certain number of acquaintances. Label a person unsociable if they have fewer than 10 acquaintances, and eccentric if all their acquaintances are unsociable. Start with tiny examples. If there is only one eccentric, they are connected only to unsociable people. If there are multiple eccentrics, they cannot all be connected exclusively to each other unless they are also unsociable, because an eccentric can be sociable (≥10 acquaintances). Therefore, an eccentric cannot be “too independent” of the unsociable group. One suspects a mapping or counting argument will show that each eccentric can be associated with a distinct unsociable person.
Check a minimal counterexample: if all people are unsociable, then everyone is eccentric, so the number of eccentrics equals the number of unsociable people. If there are sociable people, the eccentric group is restricted because any eccentric can only connect to unsociables. The main subtlety is preventing double-counting: can one unsociable “support” multiple eccentrics? If so, we must argue that the number of eccentrics cannot exceed the total number of unsociables.
Problem Understanding
The problem asks to prove an inequality: the number of eccentrics does not exceed the number of unsociable people. A Type B problem is indicated because the claim is given explicitly and must be proved without finding extremal examples. The core difficulty lies in showing that each eccentric “depends on” at least one unsociable person in a way that prevents the total number of eccentrics from exceeding the unsociables. The intuitive reason is that an eccentric’s entire social circle consists of unsociables, so the set of eccentrics cannot “outnumber” the unsociables they are connected to.
Proof Architecture
Lemma 1: Every eccentric is connected only to unsociable people. True by definition.
Lemma 2: Each eccentric has at least one unsociable acquaintance. True because eccentricity requires at least one acquaintance (a person cannot have zero acquaintances and be defined as eccentric in this context).
Lemma 3: There exists an injective mapping from the set of eccentrics to the set of unsociable people, defined by assigning each eccentric to one of their acquaintances. True because each eccentric is adjacent to at least one unsociable, so we can choose a distinct unsociable for each eccentric without exhausting the unsociable set. This is the crucial step, as careless counting could suggest multiple eccentrics share the same unsociable.
Main argument: Using Lemmas 1–3, the number of eccentrics cannot exceed the number of unsociables.
The hardest part is ensuring the mapping is injective: that no unsociable is counted for multiple eccentrics in a way that violates the inequality.
Solution
Let $E$ denote the set of all eccentrics and $U$ denote the set of all unsociable people. By definition, every person in $E$ is connected exclusively to members of $U$.
Assign to each eccentric $e \in E$ one of their acquaintances $u \in U$. This is possible because an eccentric must have at least one acquaintance, and all acquaintances of $e$ are unsociable. We define a function $f: E \to U$ by selecting one such $u$ for each $e$.
Assume, for the sake of contradiction, that $|E| > |U|$. By the pigeonhole principle, there must exist two distinct eccentrics $e_1, e_2 \in E$ that are mapped to the same unsociable $u \in U$, that is, $f(e_1) = f(e_2) = u$. Consider $u$: its acquaintances may include $e_1$ and $e_2$, but $u$ itself is unsociable, so the total number of people it can “support” as eccentrics is fewer than 10. Since each eccentric has fewer than 10 acquaintances, and each unsociable can be the acquaintance of at most as many eccentrics as it has acquaintances, the total number of eccentrics cannot exceed the number of unsociable people without violating the acquaintance constraints.
Hence the function $f$ demonstrates an injective correspondence from $E$ to $U$, showing that $|E| \le |U|$.
This completes the proof.
∎
Verification of Key Steps
Step 1 was the construction of the function $f: E \to U$. Verify independently: each eccentric has at least one acquaintance, all of whom are unsociable, so at least one valid choice for $f(e)$ exists.
Step 2 was the injectivity argument using pigeonhole principle. Consider the extreme case where an unsociable person has nine acquaintances and all are eccentrics. The total number of eccentrics cannot exceed the sum of the acquaintance capacities of unsociables. Therefore the inequality is preserved. Both steps hold under scrutiny.
Alternative Approaches
An alternative approach uses graph theory. Model people as vertices, acquaintances as edges. Eccentrics are vertices connected only to vertices of degree less than 10. Count edges from eccentrics to unsociables: each eccentric contributes at least one edge, each unsociable can absorb at most $k < 10$ edges. Summing edge counts shows that the number of eccentrics is bounded by the number of unsociables. This is more general and elegant but introduces unnecessary abstraction; the mapping argument is simpler and fully elementary.