HMMT 二月 2020 · 团队赛 · 第 6 题
HMMT February 2020 — Team Round — Problem 6
题目详情
英文原题
- [40] Let n > 1 be a positive integer and S be a collection of distinct n -element subsets of
2 n
{ 1 , 2 , . . . , 2 n } . Show that there exists A, B ∈ S such that | A ∩ B | ≤ 1.
解析
英文解析
- [40] Let n > 1 be a positive integer and S be a collection of distinct n -element subsets of
2 n
{ 1 , 2 , . . . , 2 n } . Show that there exists A, B ∈ S such that | A ∩ B | ≤ 1.
Proposed by: Michael Ren
Solution 1: Assume for the sake of contradiction that there exist no such A , B . Pair up each subsetwith its complement, like so:
{ 1 , 2 , 3 , . . . , n } ↔ { n + 1 , n + 2 , . . . , 2 n }
{ 1 , 2 , 3 , . . . , n − 1 , n + 1 } ↔ { n, n + 2 , . . . , 2 n }
{ 1 , 2 , 3 , . . . , n − 1 , n + 2 } ↔ { n, n + 1 , n + 3 , . . . , 2 n }
.
.
.
Note that for each pair, we can have at most one of the two in S . Since S has of the total number of 1
subsets with size n , it must be that we have exactly one element from each pair in S . For any s ∈ S ,2
none of the subsets that share exactly one element with s can be in S , so their complements must be 0
in S . This means that every subset with n − 1 shared elements with s must be in S . Without loss 0
of generality, assume { 1 , 2 , 3 , . . . , n } ∈ S . Then, { 2 , 3 , 4 , . . . , n + 1 } ∈ S , so { 3 , 4 , 5 , . . . , n + 2 } ∈ S .0
Continuing on in this manner, we eventually reach { n + 1 , n + 2 , . . . , 2 n } ∈ S , contradiction.
Solution 2: Let [2 n ] = { 1 , 2 , . . . , 2 n } . Consider the following cycle of 2 n − 1 sets such that any twoadjacent sets have an intersection of size 1:
{ 1 , 2 , 3 , . . . , n } ,
{ 1 , n + 1 , n + 2 , . . . , 2 n − 1 } ,
{ 1 , 2 n, 2 , 3 , . . . , n − 1 } ,
.
.
.
{ 1 , n + 2 , n + 3 , . . . , 2 n } .
If S contains two adjacent elements of the cycle then we are done. For each permutation σ of [2 n ], wecan consider the cycle C of sets obtained after applying σ , i.e. { σ (1) , σ (2) , σ (3) , . . . , σ ( n ) } and so on.
2σ
In total, each subset of [2 n ] with size n appears (2 n − 1)( n !) times across all the cycles C , soσ
∑
2 n − 1
| C ∩ S | = | S | (2 n − 1)( n !) = (2 n )!2
2σσwhere the sum is over all (2 n )! permutations of [2 n ]. This means that on average across possible
2 n − 1
cycles, of its elements are in S . Thus, if we select a cycle C uniformly at random, with positiveσprobability we will have | C ∩ S | ≥ n , so two adjacent elements in this cycle will be in S . Therefore,2
there must exist some two subsets in S that share at most one element.σ
( )
2 nn − 1
This proof will work under the weaker condition | S | > .
2 n − 1 n
Remark. A family of sets such that | A ∩ B | ≥ t for every pair of distinct sets A , B is calledt -intersecting . Ahlswede and Khachatrian solved the problem of determining the largest k -uniform t -
intersecting family. See “Katona’s Intersection Theorem: Four Proofs” or “The Complete Intersection
Theorem for Systems of Finite Sets” for exact results.