MathLabs

第1問

10個の相異なる2桁の数(十進法)からなる集合から、要素の総和が等しい2つの互いに素な部分集合を選び出せることを証明せよ。
ステップ 2/4: 鳩の巣原理を適用する
前のステップ次のステップ
ざっくり言うと

これは古典的な鳩の巣原理の適用である:箱の数より多くの物を箱に入れれば、少なくとも1つの箱には2つ以上の物が入る。

1024>946  ⟹  ∃ A≠B, sum(A)=sum(B)1024 > 946 \implies \exists\, A\neq B,\ \text{sum}(A)=\text{sum}(B)
詳しい解説

10241024 個の部分集合(「鳩」)が、たった 946946 個のとりうる和の値(「巣」)に対応するので、鳩の巣原理により、SS の相異なる部分集合 A≠BA\neq B で sum(A)=sum(B)\text{sum}(A)=\text{sum}(B) を満たすものが少なくとも一組存在する。