ホーム >> 論理 >> 要素数の等しい部分集合を適切に選ぶ
$1$ 以上 $100$ 以下の整数からなる要素数 $100$ の集合 $S$ が与えられています．この集合 $S$ から $10$ 個の数を任意に選びます．(それらの集合を $A$ とする．) このとき，$A$ の選び方によらず，$A$ から互いに交わらない $2$ つの部分集合を上手に選べば，それらの要素の和が等しくできることを示す問題です． 集合 $X$ に対して，$X$ の要素すべての和を $n(X)$ と書くことにしましょう．たとえば，$X=\{1,2,3,4\}$ なら，$n(X)=1+2+3+4=10$ です． たとえば，$A=\{1,2,…,10\}$ を選んだとすると，$A$ の部分集合として，$B=\{1,2\}，C=\{3\}$ を選べば， $$n(B)=n(C)=3$$ とできます．また，$A=\{1,2,5,9,15,20,36,44,67,100\}$ を選んだとすると，$A$ の部分集合として，$B=\{1,15,20\}，C=\{36\}$ を選べば， $$n(B)=n(C)=36$$ とできます．
$A$ の選び方は ${}_{100} \mathrm{C} _{10}$ 通りあります． 問題は，$A$ をどのように選んだとしても，$A$ から互いに交わらない $2$ つの部分集合 $B,C$ を上手に選んで， $$n(B)=n(C)$$ とできることを示すことです．
ヒント・考え方
$A$ の部分集合 $X$ の選び方の総数と，$n(X)$ のとりうる値の範囲に注目してください．
解答例
まず，明らかに $$n(A)\le 100+99+\cdots +91=955$$ が成り立ちます．したがって，$A$ の任意の部分集合 $X$ に対しても，$n(X) \le 955$ が成り立ちます．ここで，$A$ から空でない部分集合を選ぶ方法は，$2^{10}-1=1023$ 通りあります． $$955 < 1023$$ であるから，鳩ノ巣原理より，$A$ の部分集合 $B,C$ であって， $$n(B)=n(C)$$ を満たすものが必ず存在します．そこで，$B’=B-(B\cap C)，C’=C-(B\cap C)$ とおくと，$B’,C’$ はともに $A$ の部分集合であり， $$n(B’)=n(B)-n(B\cap C)=n(C)-n(B\cap C)=n(C’)$$ を満たし，さらに $B’\cap C’ =\phi$ です．したがって，この $B’,C’$ が条件を満たす $2$ つの部分集合となります．
