In a school, there are totally students, with . The students take part in clubs and in each club, there are at least members (a student may take part in more than club). Eventually, the Principal notices that: If clubs share at least common members then they have different numbers of members. Prove that
Solution
Let be the number of clubs that have members. Here, and
We will count the tuples in which the students take part in the same club that has members.
1. The first way of counting:
- Choosing club among the clubs that have members, we have ways.
- Choosing students that take part in that club, we have ways.
2. The second way of counting:
- Choosing students among all students of the school, we have ways.
- Choose club in which these two students take part. By assumption, there is at most such club.
So we get the following relation:
Hence, we have
Note that
Therefore,
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.