2004 IMO Shortlist Problems/C1
Contents
[hide]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 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 students ( a positive integer) is in exactly societies.
Find all possible values of .
Solution
Solution 1
Let us replace 10001 with an arbitrary odd integer . Suppose that some special student is a member of clubs , each with members (including our special student). We note that for , no two 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 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 societies. But each non-special student must be in exactly one of the , so . It follows that the only possible value for is . To show that this is indeed a possible value of we present the trivial case of every student belonging to the same club, which is itself the only member of separate societies.
Solution 2
Replacing the number 10001 with the variable , we will count the number of ordered triples , where is a student belonging to a club , which belongs to a society . We will denote such triples acceptable.
Now, for any student and any society , there is exactly one club which will form an acceptable triple. Thus the number of triples is .
Consider any club with members. It is in societies, so can form acceptable triples. If denotes the set of all clubs, then this implies that
.
But since any pair of students belong to exactly one club, it follows that , or . Therefore .
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.