In a school there are students. Each student must join exactly clubs. Given that there is a common club joined by every students, but there is no common club joined by all students, find the smallest possible value of .
Solution
The answer is .
We first show . We list the students as and the clubs as . Consider the following construction. For , student joins clubs . For , student joins the same clubs as . Then we can see every students have a common club, but all students do not have a common club.
Now we show . Suppose a student joins clubs . Because all students do not join a common club, for each , there is a student not joining the club . Hence the students do not have a common club, forcing . The proof is complete.
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.