問題の説明

集合 $S=\{1,2,...,10\}$ の空でない部分集合は $2^{10}-1$ 個あります．このうち，$2^9+1$ 以上 (つまり，だいたい半分より多く)の部分集合を好きなように選びます．どのように選んだとしても，そのうちのどれか ($A_k$) は選んだ他の $2$ つの集合 ($A_i,A_j$) の和集合でかけることを示す問題です．

ヒント・考え方

$2^9+1$ という数は大きすぎるので，手始めに，もっと簡単な数で考察してみましょう．
たとえば，$\{1,2\}$ から $3$ 個の空でない部分集合を選ぶとすると，それは $\{1\},\{2\},\{1,2\}$ しかないので， $$\{1\}\cup \{2\}=\{1,2\}$$ が成り立ちます．
また，$\{1,2,3\}$ から $5$ 個以上の空でない部分集合を選ぶとすると，題意が成り立つことは簡単な計算で確かめられます．
たとえば，$\{1\},\{2\},\{2,3\},\{1,3\},\{1,2,3\}$ を選ぶと，$\{1\}\cup \{2,3\}=\{1,2,3\}$ となります．
このように考えていくと，問題を一般化したつぎの補題が成り立ちそうだという気になります．

補題　$n$ を $2$ 以上の整数，$m$ を $2^{n-1}+1$ 以上の整数とする．$m$ 個の集合 $A_1,...,A_m$ を相異なる $\{1,2,...,n\}$ の空でない部分集合とする．このとき，$A_i \cup A_j=A_k$ を満たす相異なる整数 $i,j,k$ が存在する．

解答例

以下の補題を示します．

補題　$n$ を $2$ 以上の整数，$m$ を $2^{n-1}+1$ 以上の整数とする．$m$ 個の集合 $A_1,...,A_m$ を相異なる $\{1,2,...,n\}$ の空でない部分集合とする．このとき，$A_i \cup A_j=A_k$ を満たす相異なる整数 $i,j,k$ が存在する．

$m=2^{n-1}+1$ のときに示せば $m\ge 2^{n-1}+1$ の場合も当然示せたことになります．
$n$ に関する帰納法で示していきます．
$n= 2$ のとき，$S=\{1,2\}$ の空でない $3$ 個の部分集合は $\{1\},\{2\},\{1,2\}$ で， $$\{1\}\cup \{2\}=\{1,2\}$$ なので，題意は成り立ちます．
$n\ge 2$ のとき，題意が成り立つと仮定します．すなわち，『$2^{n-1}+1$ 個の集合 $A_1,...,A_{2^{n-1}+1}$ を相異なる $\{1,2,...,n\}$ の空でない部分集合とするとき，$A_i \cup A_j=A_k$ を満たす相異なる整数 $i,j,k$ が存在する．』と仮定します．
このとき，『$\{1,2,...,n+1\}$ から $2^{n}+1$ 個の相異なる空でない部分集合 $A'_1,...,A'_{2^n+1}$ をどのようにえらんでも，$A'_i \cup A'_j=A'_k$ を満たす相異なる整数 $i,j,k$ が存在すること』を示します．

さて，$\{1,2,...,n+1\}$ から $2^{n}+1$ 個の相異なる空でない部分集合を選びます．そのうち，元 $\{n+1\}$ を含む部分集合の個数を $x$，元 $\{n+1\}$ を含まない部分集合の個数を $y$ とします．当然 $x+y=2^n+1$ が成り立ちます．以下，状況を三通りに場合分けして考えます．

$(i)$ $y\ge 2^{n-1}+1$ のとき
このとき，帰納法の仮定から，題意が成り立つことは明らかです．

$(ii)$ $x\ge 2^{n-1}+2$ のとき
このとき，$\{n+1\}$ を含む部分集合のうち，$\{n+1\}$ と異なるものは少なくとも $2^{n-1}+1$ 個以上あるので，帰納法の仮定より，題意が成り立ちます．

$(iii)$ $y\le 2^{n-1}$ かつ $x\le 2^{n-1}+1$ のとき
このとき，$x+y=2^n+1$ より，$x=2^{n-1}+1,y=2^{n-1}$ となります．
・$(iii-a)$ 元 $\{n+1\}$ を選んでいないとき
このとき，$\{n+1\}$ を含む部分集合のうち，$\{n+1\}$ と異なるものが $2^{n-1}+1$ 個あるので，帰納法の仮定より，題意が成り立ちます．
・$(iii-b)$ 元 $\{n+1\}$ を選んでいるとき
このときの状況をもう一度整理します．$\{1,2,...,n+1\}$ から，$\{n+1\}$ を含む部分集合のうち，$\{n+1\}$ と異なるものを $2^{n-1}$ 個と元 $\{n+1\}$，それから，$\{n+1\}$ を含まない部分集合を $2^{n-1}$ 個選んでいます．選んだ部分集合から $\{n+1\}$ を取り除くと，$\{1,2,...,n\}$ から合計 $2^n$ 個の部分集合を選んでいます．したがって，鳩ノ巣原理より，少なくとも $1$ つは ($\{n+1\}$ をとりのぞいた結果として)同じ集合を選んでいます．(それを $A'_i$ とおきます) 以上より，$A'_i$，$A'_i\cup \{n+1\}$，$\{n+1\}$ を選んでいるので， $$A'_i\cup \{n+1\}=A'_i\cup \{n+1\}$$ となり，題意が成り立ちます．

以上 $(i),(ii),(iii)$ よりいずれの場合も題意が成り立つことが示されました．

---