HMMT 二月 2016 · 团队赛 · 第 9 题

英文解析

9. [ 40 ] Fix positive integers r > s , and let F be an infinite family of sets, each of size r , no two of whichshare fewer than s elements. Prove that there exists a set of size r − 1 that shares at least s elementswith 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 nosuch 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 actuallyessential).
   ′ ′
   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 acontradiction 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. Thenthere 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 andr > 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, thereexists 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,Zminimality 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 ⊆ Xcontradicting our assumption.