Maths Olympiad Prep

Library / /340 of 377

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

At a certain college, there are 10 clubs and some number of students. For any two different students, there is some club such that exactly one of the two belongs to that club. For any three different students, there is some club such that either exactly one or all three belong to that club. What is the largest possible number of students?

Solution

Solution:

Let CC be the set of clubs; each student then corresponds to a subset of CC (the clubs to which that student belongs). The two-student condition implies that these subsets must be all distinct. Now (assuming there is more than one student) some student belongs to a nonempty set SS of clubs. For every subset TCT \subseteq C, let f(T)f(T) be the subset of CC consisting of those clubs that are in exactly one of SS and TT (so that f(T)=(ST)(ST)f(T) = (S \cup T) - (S \cap T)). It is straightforward to check that f(f(T))=Tf(f(T)) = T and f(T)Tf(T) \neq T, so that the collection of all 2102^{10} subsets of CC is partitioned into pairs {T,f(T)}\{T, f(T)\}. Moreover,
as long as SS is distinct from TT and f(T)f(T), every club is in either none or exactly two of the sets S,TS, T, and f(T)f(T), so we cannot have a student corresponding to TT and another corresponding to f(T)f(T). This puts an upper bound of 513 possible students (one for SS, one for =f(S)\emptyset = f(S), and one for each of the 511 other pairs). On the other hand, if we take some club cc, we can have one student belonging to no clubs and 512 other students all belonging to cc and to the 512 possible subsets of the other 9 clubs, respectively. It is readily checked that this arrangement meets the conditions - for the three-student condition, either all three students are in cc, or one is the student who belongs to no clubs and we reduce to the two-student condition - so 513 is achievable.

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.