Writeup: IMO 2004 Shortlist C1

07 Jun, 2025

Problem Statement

There are $10001$ students at an university. Some students join together to form several clubs (a student may belong to different clubs). Some clubs join together to form several societies (a club may belong to different societies). There are a total of $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 $2m+1$ students ($m$ is a positive integer) is in exactly $m$ societies.

Find all possible values of $k$.

Solution:

This problem was so troll lmao. I tried to do make up so many random functions to solve this problem but I realized the solution was actually really easy.

Consider the set $S$ of ordered triples (student, club, society). We know from (iii) and (ii) that $|S|=\sum \text{\# of students in each club}·\text{\# of societies the clubs belongs to}=\sum \frac{\text{\# of students in each club}·\text{\# of students in each club - 1}2}{}$ but we also know that $|S|=\text{\# of students}·\text{\# of societies}.$ But from (i) we know that $\sum \frac{\text{\# of students in each club}·\text{\# of students in each club - 1}}{2}=10001·5000$ so $k=5000.$