HMMT 十一月 2016 · 冲刺赛 · 第 26 题

英文解析

26. [ 13 ] Find the number of ways to choose two nonempty subsets X and Y of { 1 , 2 , . . . , 2001 } , such that
    | Y | = 1001 and the smallest element of Y is equal to the largest element of X .
    Proposed by: Allen Liu
    2000
    Answer: 2
    We claim that there is a bijection between pairs ( X, Y ) and sets S with at least 1001 elements. To get
    S from X and Y , take S = X ∪ Y , which contains Y and thus has at least 1001 elements. To form
    ( X, Y ) from S , make Y the largest 1001 elements of S , and make X everything except the largest 1000
    elements of S . Therefore we need to count the number of subsets of { 1 , 2 , . . . , 2001 } with at least 1001
    elements. For every subset of { 1 , 2 , . . . , 2001 } , either it or its complement has at least 1001 elements,
    1 2000
    2001
    so number of possible subsets is · 2 = 2 .
    4 3 22