ホーム >> 論理 >> 要素数の等しい部分集合を適切に選ぶ

問題の説明

$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$ つの部分集合となります.