問 $S=\{1,2,3,...,98,99,100\}$ とする.集合 $S$ から要素数 $10$ の部分集合 $A$ をどのように選んだとしても,$A$ から互いに交わらない $2$ つの部分集合を適当に選んで,それらの要素の和が等しくできることを示せ.
2018/9/6
論理
★★☆☆☆
$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$ つの部分集合となります.