HMMT 二月 2016 · 团队赛 · 第 9 题
HMMT February 2016 — Team Round — Problem 9
题目详情
- [ 40 ] Fix positive integers r > s , and let F be an infinite family of sets, each of size r , no two of which share fewer than s elements. Prove that there exists a set of size r − 1 that shares at least s elements with each set in F .
解析
- [ 40 ] Fix positive integers r > s , and let F be an infinite family of sets, each of size r , no two of which share fewer than s elements. Prove that there exists a set of size r − 1 that shares at least s elements with each set in F . Proposed by: Victor Wang This is a generalization of 2002 ISL C5. Solution 1. Say a set S s -meets F if it shares at least s elements with each set in F . Suppose no such set of size (at most) r − 1 exists. (Each S ∈ F s -meets F by the problem hypothesis.) ′ Let T be a maximal set such that T ⊆ S for infinitely many S ∈ F , which form F ⊆ F (such T exists, since the empty set works). Clearly | T | < r , so by assumption, T does not s -meet F , and there exists ′ U ∈ F with | U ∩ T | ≤ s − 1. But U s -meets F , so by pigeonhole, there must exist u ∈ U \ T belonging ′ to infinitely many S ∈ F , contradicting the maximality of T . Comment. Let X be an infinite set, and a , . . . , a elements not in X . Then F = { B ∪ { x } : 1 2 r − 2 − s B ⊆ { a , . . . , a } , | B | = r − 1 , x ∈ X } shows we cannot replace r − 1 with any smaller number. 1 2 r − 2 − s Solution 2. We can also use a more indirect approach (where the use of contradiction is actually essential). ′ ′ Fix S ∈ F and a ∈ S . By assumption, S \ { a } does not s -meet F , so there exists S ∈ F such that S ′ contains at most s − 1 elements of S \ { a } , whence S ∩ S is an s -set containing a . We will derive a contradiction from the following lemma: Lemma. Let F, G be families of r -sets such that any f ∈ F and g ∈ G share at least s elements. Then there exists a finite set H such that for any f ∈ F and g ∈ G , | f ∩ g ∩ H | ≥ s . Proof. Suppose not, and take a counterexample with r + s minimal; then F, G must be infinite and r > s > 0. Take arbitrary f ∈ F and g ∈ G ; then the finite set X = f ∪ g meets F, G . For every subset Y ⊆ X , 0 0 0 0 let F = { S ∈ F : S ∩ X = Y } ; analogously define G . Then the F , G partition F, G , respectively. Y Y Y Y For any F and y ∈ Y , define F ( y ) = { S \ { y } : S ∈ F } . Y Y Y Now fix subsets Y, Z ⊆ X . If one of F , G is empty, define H = ∅ . Y Z Y,Z Otherwise, if Y, Z are disjoint, take arbitrary y ∈ Y , z ∈ Z . By the minimality assumption, there exists finite H such that for any f ∈ F ( y ) and g ∈ G ( z ), | f ∩ g ∩ H | ≥ s . Y,Z Y Z Y,Z If Y, Z share an element a , and s = 1, take H = { a } . Otherwise, if s ≥ 2, we find again by Y,Z minimality a finite H ( a ) such that for f ∈ F ( a ) and g ∈ G ( a ), | f ∩ g ∩ H | ≥ s − 1; then take Y,Z Y Z Y,Z H = H ( a ) ∪ { a } . Y,Z Y,Z ⋃ Finally, we see that H = H shares at least s elements with each f ∩ g (by construction), Y,Z Y,Z ⊆ X contradicting our assumption.