第1問

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

ステップ 3/4: 共通部分を取り除いて互いに素な集合を得る

ざっくり言うと

総重量が等しい2つの異なる山は、すべての品物の重さが正である限り、一方がもう一方に完全に含まれることはあり得ない。したがって共通の品物を取り除いても、両側にまだ何かが残る。

A'=A\setminus B,\quad B'=B\setminus A

詳しい解説

$A'=A\setminus B$ 、 $B'=B\setminus A$ とおく。この2つの集合は構成上互いに素である。 $S$ の元はすべて正であるから、 $A\neq B$ より $A\not\subseteq B$ かつ $B\not\subseteq A$ が従う(そうでなければ、すべての元が正である以上、真部分集合の和は全体集合の和より真に小さいため、2つの和は等しくなり得ない)。したがって $A'$ と $B'$ はともに空でない。