Difference between revisions of "2004 IMO Shortlist Problems/C1"
m (→Resources: fixed link) |
|||
Line 37: | Line 37: | ||
* [[2004 IMO Shortlist Problems]] | * [[2004 IMO Shortlist Problems]] | ||
− | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p= | + | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=258304#p258304 Discussion on AoPS/MathLinks] |
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] |
Latest revision as of 21:06, 7 May 2007
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.