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 subset with 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 } . . . 1 Note that for each pair, we can have at most one of the two in S . Since S has of the total number of 2 subsets with size n , it must be that we have exactly one element from each pair in S . For any s ∈ S , 0 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 . 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 two adjacent 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 ], we can 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 2 | C ∩ S | = | S | (2 n − 1)( n !) = (2 n )! σ 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 σ 2 probability we will have | C ∩ S | ≥ n , so two adjacent elements in this cycle will be in S . Therefore, σ there must exist some two subsets in S that share at most one element. ( ) 2 n n − 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 called t -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.