第1問

10個の相異なる2桁の数(十進法)からなる集合から、要素の総和が等しい2つの互いに素な部分集合を選び出せることを証明せよ。

ステップ 1/4: 部分集合の個数ととりうる和の個数を数える

ざっくり言うと

10個の数から部分集合を選ぶ方法の数は、その和として取りうる値の数をはるかに上回るので、いくつかの和は必ず重複する——これが鳩の巣原理の種となる。

2^{10}=1024\text{ subsets, sums lie in }[0,945]

詳しい解説

$S=\{a_1,\dots,a_{10}\}$ を10個の相異なる2桁の数( $10\le a_i\le 99$ )とする。集合 $S$ にはちょうど $2^{10}=1024$ 個の部分集合がある(空集合を含む)。各部分集合の和は非負整数であり、最大でも $90+91+\cdots+99=945$ (2桁の数のうち最大の10個の和)を超えないので、すべての部分集合の和は $\{0,1,\dots,945\}$ というわずか $946$ 個の値しかとりうる集合に属する。