2004 IMO Shortlist Problems/C1

Problem

(Puerto Rico) There are 10001 students at an university (sic). Somer students join together to form several clubs (a student may belong to different clubs). Some clubs join together to form societies (a club may belong to different societies. There are a total of $\displaystyle k$ societies. Suppose that the following conditions hold:
(i) Each pair of students are in exactly one club.
(ii) For each student and each society, the student is in exactly one club of the society.
(iii) Each club has an odd number of students. In addition, a club with $\displaystyle 2m+1$ students ( $\displaystyle m$ a positive integer) is in exactly $\displaystyle m$ societies.

Find all possible values of $\displaystyle k$ .

Solution

Solution 1

Let us replace 10001 with an arbitrary odd integer $\displaystyle n$ . Suppose that some special student is a member of clubs $C_1, \ldots, C_j$ , each with $2m_1 + 1, \ldots, 2m_j + 1$ members (including our special student). We note that for $1 \le i \le j$ , no two $\displaystyle C_i$ may contain a common student other than our special student, or this common student and the special students would together be members of more than one society. Furthermore, no two of the $\displaystyle C_i$ may belong to a common society, or our special student would be a member of two clubs of the same society. Since our special student is a member of some club of every society, it follows that there $k= \sum_{i=1}^j m_i$ societies. But each non-special student must be in exactly one of the $\displaystyle C_i$ , so $\sum_{i=1}^j 2m_i = n-1$ . It follows that the only possible value for $\displaystyle k$ is $\frac{n-1}{2}$ . To show that this is indeed a possible value of $\displaystyle k$ we present the trivial case of every student belonging to the same club, which is itself the only member of $\frac{n-1}{2}$ separate societies.

Solution 2

Replacing the number 10001 with the variable $\displaystyle n$ , we will count the number of ordered triples $\displaystyle (a,C,S)$ , where $\displaystyle a$ is a student belonging to a club $\displaystyle {} C$ , which belongs to a society $\displaystyle S$ . We will denote such triples acceptable.

Now, for any student $\displaystyle a$ and any society $\displaystyle S$ , there is exactly one club which will form an acceptable triple. Thus the number of triples is $\displaystyle nk$ .

Consider any club $\displaystyle {} C$ with $\displaystyle |C|$ members. It is in $\frac{|C| -1}{2}$ societies, so $\displaystyle {} C$ can form $\frac{|C|(|C|-1}{2}$ acceptable triples. If $\mathcal{C}$ denotes the set of all clubs, then this implies that

$nk = \sum_{C \in \mathcal{C}} \frac{|C|(|C|-1)}{2} = \sum_{C \in \mathcal{C}} {|C| \choose 2}$ .

But since any pair of students belong to exactly one club, it follows that ${n \choose 2} = \sum_{C \in \mathcal{C}} {|C| \choose 2}$ , or $\frac{n(n-1)}{2} = nk$ . Therefore $k = \frac{n-1}{2}$ .

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Page

Toolbox

Search