Kvant Math Problem 707

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m20s
Source on kvant.digital

Problem

Each student in a class participates in at most two clubs, and for any pair of students, there is a club in which they both participate. Prove that there exists a club in which at least $\dfrac{2}{3}$ students from this class are members.

A. F. Sidorenko

Exploration

Let the clubs be represented by sets of students. Each student belongs to at most two clubs. Any two students have a common club.

A useful reformulation is obtained by looking at the pattern of memberships of a student. Since each student belongs to at most two clubs, every student is either of type $A$ (belongs to exactly one club $A$) or of type $A\cap B$ (belongs to exactly two clubs $A,B$).

Suppose there are three clubs $A,B,C$. A student belonging only to $A$ and a student belonging only to $B$ do not share a club, so they cannot both exist. More generally, if there are students belonging only to two different clubs, the condition fails.

It is natural to translate the problem into a graph. Let the clubs be vertices. A student belonging to exactly two clubs corresponds to the edge joining those clubs. A student belonging only to one club corresponds to a loop at the corresponding vertex. The condition that every pair of students share a club means that any two corresponding edges or loops intersect in a vertex.

Thus we obtain a family of edges in a graph such that every two edges intersect. Since ordinary edges have size $2$ and loops have size $1$, this is a family of subsets of the vertex set of size at most $2$, pairwise intersecting.

What can such a family look like? If there are two distinct non-loop edges, say $AB$ and $AC$, then every other edge must meet both of them. Hence every other edge contains $A$, because an edge meeting $AB$ and $AC$ without containing $A$ would have to be $BC$, but then $BC$ is disjoint from neither, yet another edge could create difficulties. Testing examples quickly suggests a stronger statement: a pairwise intersecting family of $1$- and $2$-element sets is either a star, all containing one vertex, or consists of the three edges $AB,BC,CA$ of a triangle.

The triangle configuration is the only obstruction to having a common club for all students. In that case there are three clubs and students are distributed among the three pairwise intersections. Then one of the clubs contains at least two of the three groups, giving at least $\frac23$ of all students.

The step most likely to hide an error is the classification of pairwise intersecting families of subsets of size at most $2$. That part must be proved carefully.

Problem Understanding

We are given a class of students and a collection of clubs. Every student belongs to at most two clubs. For every pair of students, there exists a club containing both of them. We must prove that some club contains at least $\frac23$ of all students.

This is a Type B problem.

The core difficulty is to understand all possible patterns of club memberships compatible with the condition that every two students share a club. Since students belong to at most two clubs, each student can be represented by a subset of clubs of size at most $2$. The condition becomes a pairwise intersection condition on these subsets.

Proof Architecture

Consider the family of membership sets of students, where each set consists of the clubs to which that student belongs.

Lemma 1. Any two membership sets intersect.

This is a direct translation of the hypothesis that every pair of students belong together to some club.

Lemma 2. A pairwise intersecting family of subsets of a set, each of size at most $2$, is either a star, meaning all sets contain a fixed club, or it is contained in the three sets ${A,B},{B,C},{C,A}$ for some clubs $A,B,C$.

Take one two-element set ${A,B}$; if another set does not contain $A$, pairwise intersection forces it to contain $B$, and a short case analysis yields the classification.

Lemma 3. In the star case, one club contains every student.

Every membership set contains the center club.

Lemma 4. In the triangle case, some club contains at least $\frac23$ of all students.

The three membership types are ${A,B},{B,C},{C,A}$; one of the three pair-sums of their populations is at least two thirds of the total.

The most delicate lemma is Lemma 2, because it classifies all pairwise intersecting families of $1$- and $2$-element sets.

Solution

Let $S$ be the set of students, and let $\mathcal C$ be the set of clubs.

For each student $x$, define

$$M(x)\subseteq \mathcal C$$

to be the set of clubs to which $x$ belongs. By hypothesis,

$$|M(x)|\le 2$$

for every student $x$.

The condition of the problem states that for any two students $x$ and $y$, there exists a club containing both. Equivalently,

$$M(x)\cap M(y)\neq\varnothing$$

for all students $x,y$.

Thus the family

$$\mathcal F={M(x):x\in S}$$

is a pairwise intersecting family of subsets of $\mathcal C$, each of size at most $2$.

We classify such families.

If every set in $\mathcal F$ has size $1$, then pairwise intersection implies that all of them are the same singleton. Hence there is a club belonging to every set in $\mathcal F$, and therefore every student belongs to that club. The conclusion is immediate.

Assume from now on that some member of $\mathcal F$ has size $2$. Choose one such set and denote it by

$${A,B}.$$

Suppose every set in $\mathcal F$ contains $A$. Then club $A$ contains every student, and again the conclusion is immediate.

It remains to consider the case when some set in $\mathcal F$ does not contain $A$. Since it must intersect ${A,B}$, it contains $B$. Let this set be $T$.

If $T={B}$, then every member of $\mathcal F$ must intersect both ${A,B}$ and ${B}$. Hence every member contains $B$. Thus club $B$ contains every student.

Therefore we may assume

$$T={B,C}$$

with $C\ne A$.

Take any set $U\in\mathcal F$. Since $U$ intersects both ${A,B}$ and ${B,C}$, we examine the possibilities.

If $B\in U$, then, because $|U|\le2$, the set $U$ is one of

$${B},\quad {A,B},\quad {B,C}.$$

If $B\notin U$, then $U$ must intersect ${A,B}$, so $A\in U$. Also $U$ must intersect ${B,C}$, so $C\in U$. Since $|U|\le2$,

$$U={A,C}.$$

Consequently every member of $\mathcal F$ is one of

$${B},\quad {A,B},\quad {B,C},\quad {A,C}.$$

If ${B}\in\mathcal F$, then every member of $\mathcal F$ intersects ${B}$, hence every member contains $B$. Thus club $B$ contains every student.

The only remaining possibility is that every member of $\mathcal F$ belongs to the family

$${{A,B},{B,C},{C,A}}.$$

Let

$$n_{AB},\quad n_{BC},\quad n_{CA}$$

denote the numbers of students of these three types. The total number of students is

$$N=n_{AB}+n_{BC}+n_{CA}.$$

Club $A$ contains exactly the students of types ${A,B}$ and ${A,C}$, so its membership is

$$n_{AB}+n_{CA}.$$

Similarly, clubs $B$ and $C$ contain

$$n_{AB}+n_{BC}, \qquad n_{BC}+n_{CA}$$

students respectively.

The sum of these three numbers equals

$$(n_{AB}+n_{CA})+(n_{AB}+n_{BC})+(n_{BC}+n_{CA}) =2N.$$

Hence their average is

$$\frac{2N}{3}.$$

At least one of the three numbers is therefore at least its average. Thus one of the clubs contains at least

$$\frac{2N}{3}$$

students.

This proves that there exists a club containing at least two thirds of all students.

This completes the proof.

∎

Verification of Key Steps

The classification step must exclude all configurations other than a star or a triangle. Starting from ${A,B}$ and ${B,C}$, any additional set $U$ must intersect both. If $B\notin U$, intersection with ${A,B}$ forces $A\in U$, and intersection with ${B,C}$ forces $C\in U$. Since $|U|\le2$, this gives $U={A,C}$. If $B\in U$, then $U$ can only be ${B}$, ${A,B}$, or ${B,C}$. No other set is possible.

The treatment of the singleton ${B}$ requires care. Once ${B}$ belongs to the family, every other member must intersect it. Intersection with a singleton means containing $B$. Thus all membership sets contain $B$, so club $B$ contains every student. Forgetting this case would leave a gap in the classification.

In the triangle case, the estimate $\frac23$ comes from averaging. The club sizes are

$$n_{AB}+n_{CA},\quad n_{AB}+n_{BC},\quad n_{BC}+n_{CA}.$$

Their sum is exactly $2N$. Since three numbers with sum $2N$ have maximum at least $\frac{2N}{3}$, one club contains at least two thirds of the students. No stronger universal bound follows from this argument.

Alternative Approaches

A graph-theoretic formulation gives a compact proof. Represent clubs by vertices. A student belonging to clubs $A$ and $B$ is represented by the edge $AB$, while a student belonging only to club $A$ is represented by a loop at $A$. The hypothesis says that any two such edges intersect. One then uses the standard fact that a pairwise intersecting family of edges in a graph is either a star or the three edges of a triangle. The remainder of the argument is identical: a star gives a club containing all students, and a triangle yields the $\frac23$ bound by averaging.

The set-theoretic approach used above is preferable because it stays closer to the language of the problem and requires no additional graph terminology.