HMMT 二月 2003 · COMB 赛 · 第 9 题
HMMT February 2003 — COMB Round — Problem 9
题目详情
- 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? 1
解析
- 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: 513 Let C be the set of clubs; each student then corresponds to a subset of C (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 S of clubs. For every subset T ⊆ C , let f ( T ) be the subset of 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 , so 10 that the collection of all 2 subsets of C is partitioned into pairs { T, f ( T ) } . Moreover, 3 as long as S is distinct from T and f ( T ), every club is in either none or exactly two of the sets S, T , and f ( T ), so we cannot have a student corresponding to T and another corresponding 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 we take some club c , we can have one student belonging to no clubs and 512 other students all belonging to c 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 c , or one is the student who belongs to no clubs and we reduce to the two-student condition — so 513 is achievable.