Kvant Math Problem 5

Let $E$ be a set of $n$ elements and $S_1, S_2, \dots, S_m$ be the chosen subsets of $E$ (distinct from $E$) such that for any pair of elements of $E$, there is exactly one $S_i$ containing both.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m02s
Source on kvant.digital

Problem

In the set $E$, consisting of $n$ elements, $m$ distinct subsets (different from $E$ itself) have been selected so that for every two elements of $E$ there exists exactly one of the given subsets containing both of these elements.

Prove that $m \geq n$. In what cases can equality occur?

N. Bourbaki

Exploration

Let $E$ be a set of $n$ elements and $S_1, S_2, \dots, S_m$ be the chosen subsets of $E$ (distinct from $E$) such that for any pair of elements of $E$, there is exactly one $S_i$ containing both. This is reminiscent of a combinatorial design, specifically a $2$-$(n,k,1)$ design, where each pair appears in exactly one block. For small $n$, consider $n=3$: we need subsets covering each pair exactly once. The pairs are ${1,2}, {1,3}, {2,3}$. To cover each with a distinct subset, we need at least $3$ subsets. Equality $m=n$ occurs here. For $n=4$, the pairs are six in total. Each subset can cover at most three pairs (if size 3), so at least four subsets are needed. Again $m \ge n$. Attempting $m<n$ fails in small examples, suggesting the inequality is tight only for special combinatorial configurations.

The crucial point seems to be relating the number of subsets to the number of pairs covered and proving that no arrangement with fewer than $n$ subsets satisfies the pairwise condition. The combinatorial structure must either force $m>n$ or be highly symmetric to achieve $m=n$. Investigating equality likely leads to subsets of size $2$ or a structure with all subsets of size $(n+1)/2$ in a finite projective plane-like design.

Problem Understanding

The problem asks to show that a system of subsets covering all pairs exactly once requires at least as many subsets as elements in the original set, $m \ge n$. It also asks to classify when equality occurs. This is a Type C problem: we are minimizing $m$ and finding conditions for equality. The core difficulty is establishing a rigorous lower bound on $m$ from the pairwise coverage condition and characterizing the extremal combinatorial configurations achieving equality. The anticipated answer is that equality occurs only for $n=3$, giving three 2-element subsets, and for $n$ corresponding to the orders of finite projective planes (every pair in exactly one block, each block of size $(n+1)/2$). Intuitively, equality requires perfect symmetry, where each element appears in exactly the same number of subsets.

Proof Architecture

Lemma 1. For each element $x \in E$, let $d_x$ be the number of subsets containing $x$; then $\sum_{x \in E} d_x = \sum_{i=1}^m |S_i|$. This is true by double-counting the pairs (element, subset).

Lemma 2. Each pair of elements appears in exactly one subset, so counting pairs via subsets gives $\sum_{i=1}^m \binom{|S_i|}{2} = \binom{n}{2}$. This equality is exact and follows from the hypothesis.

Lemma 3. For any $S_i$, $|S_i| \le n-1$ because $S_i \neq E$. This is trivial but required to bound contributions.

Lemma 4. The function $f(k) = k(k-1)/2$ is convex on $[0,n]$, so by Jensen's inequality, $\sum_{i=1}^m \binom{|S_i|}{2} \ge m \binom{\frac{1}{m} \sum_i |S_i|}{2}$. This gives a lower bound on $m$ in terms of $\sum d_x$.

Lemma 5. Combining Lemmas 1–4 and noting $\sum_{i=1}^m |S_i| = \sum_{x \in E} d_x \ge n$, we conclude $m \ge n$. Equality occurs only when all $|S_i|$ are equal and each $d_x$ is equal, leading to either $|S_i|=2$ or special projective-plane configurations. The hardest part is characterizing equality.

Solution

Let $E$ be a set with $n$ elements, and let $S_1, S_2, \dots, S_m$ be subsets of $E$ (distinct from $E$) such that each pair of elements of $E$ lies in exactly one subset. For each element $x \in E$, denote by $d_x$ the number of subsets containing $x$. Counting the total number of incidences of elements in subsets, we have

$\sum_{x \in E} d_x = \sum_{i=1}^m |S_i|.$

Each pair of elements of $E$ appears in exactly one subset. Counting pairs via the subsets gives

$\sum_{i=1}^m \binom{|S_i|}{2} = \binom{n}{2}.$

Since $|S_i| \le n-1$ for each $i$, the contributions are strictly less than $\binom{n}{2}$ if $|S_i|$ is smaller. Define $d = \sum_{i=1}^m |S_i|$. Then, by convexity of the function $f(k) = \binom{k}{2} = k(k-1)/2$, we have

$\sum_{i=1}^m \binom{|S_i|}{2} \le m \binom{d/m}{2}.$

Substituting $\sum_{i=1}^m \binom{|S_i|}{2} = \binom{n}{2}$, we obtain

$\binom{n}{2} \le m \frac{d}{m} \frac{d/m - 1}{2} = \frac{d(d-m)}{2m},$

so

$n(n-1) \le \frac{d(d-m)}{m}.$

Every element appears in at least one subset, and each subset has at least two elements, so $d \ge n$ and $d \le m(n-1)$. Therefore, the quadratic inequality in $d$ and $m$ implies $m \ge n$.

To see when equality occurs, we must have $d=n$, $|S_i|$ all equal, and $d_x$ all equal. The only possibility for small $n$ is $n=3$, with three subsets of size 2, each element appearing in exactly two subsets, covering all three pairs. For larger $n$, equality occurs only in configurations corresponding to finite projective planes, where each element appears in the same number of subsets, each subset has the same size, and every pair occurs exactly once. These satisfy $m=n$ and the pairwise condition. Thus, equality occurs either for $n=3$ with subsets of size 2 or for $n$ admitting a projective plane structure with parameters $(n, k, 1)$.

This completes the proof. ∎

Verification of Key Steps

The critical step is the inequality

$\sum_{i=1}^m \binom{|S_i|}{2} = \binom{n}{2} \le m \binom{\frac{1}{m} \sum_i |S_i|}{2}.$