返回题库

HMMT 二月 2020 · 团队赛 · 第 6 题

HMMT February 2020 — Team Round — Problem 6

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  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.
解析

英文解析

  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.