HMMT 二月 2003 · COMB 赛 · 第 9 题

英文解析

9. At a certain college, there are 10 clubs and some number of students. For any twodifferent students, there is some club such that exactly one of the two belongs to thatclub. For any three different students, there is some club such that either exactly oneor all three belong to that club. What is the largest possible number of students?
   Solution: 513
   Let C be the set of clubs; each student then corresponds to a subset of C (the clubsto which that student belongs). The two-student condition implies that these subsetsmust be all distinct. Now (assuming there is more than one student) some studentbelongs to a nonempty set S of clubs. For every subset T ⊆ C , let f ( T ) be the subsetof C consisting of those clubs that are in exactly one of S and T (so that f ( T ) =
   ( S ∪ T ) − ( S ∩ T )). It is straightforward to check that f ( f ( T )) = T and f ( T ) 6 = T , sothat the collection of all 2 subsets of C is partitioned into pairs { T, f ( T ) } . Moreover,10
   as long as S is distinct from T and f ( T ), every club is in either none or exactly two of 3
   the sets S, T , and f ( T ), so we cannot have a student corresponding to T and anothercorresponding to f ( T ). This puts an upper bound of 513 possible students (one for S ,
   one for ∅ = f ( S ), and one for each of the 511 other pairs). On the other hand, if wetake some club c , we can have one student belonging to no clubs and 512 other studentsall belonging to c and to the 512 possible subsets of the other 9 clubs, respectively. Itis readily checked that this arrangement meets the conditions — for the three-studentcondition, either all three students are in c , or one is the student who belongs to noclubs and we reduce to the two-student condition — so 513 is achievable.