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

HMMT November 2016 — Guts Round — Problem 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 . 4 3 2

解析

[ 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 . 2 4 3 2