Competition problem — Combinatorics

Library / /42 of 136

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it Hong Kong

Let $n$ be an integer greater than $1$ . In a school there are $n^2 - n + 2$ clubs and each club has exactly $n$ members. Each pair of clubs has exactly one member in common. Show that there is one student belonging to all of the clubs.

Solution

Consider an arbitrary club $C_1$ . Since it shares a common member with each of the other $n^2 - n + 1$ clubs, by the pigeonhole principle, there is a member in $C_1$ who is also a member of at least
$\left\lfloor \frac{n^2 - n + 1}{n} \right\rfloor = n$
clubs. Suppose $X$ is a member of the clubs $C_1, C_2, \dots, C_{n+1}$ . For any other club $C_k$ , since it shares a common member with each of $C_1, C_2, \dots, C_{n+1}$ , by the pigeonhole principle, there is a member in $C_k$ who is also a member of at least
$\left\lfloor \frac{n+1}{n} \right\rfloor = 2$
clubs among $C_1, C_2, \dots, C_{n+1}$ . As the only common member in $C_1, C_2, \dots, C_{n+1}$ is $X$ , this member must also be $X$ . This shows $X$ is a member of $C_k$ for all $k$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.