MathLabs

第1問

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

共通の品物を両方の山から取り除くということは、両側から同じ重さを差し引くことを意味するので、もともと総和が等しかったなら、その後も等しいままである——そして今や残った山同士は重なり合っていない。

sum(A′)=sum(A)−sum(A∩B)=sum(B)−sum(A∩B)=sum(B′)\text{sum}(A')=\text{sum}(A)-\text{sum}(A\cap B)=\text{sum}(B)-\text{sum}(A\cap B)=\text{sum}(B')
詳しい解説

sum(A)=sum(A∩B)+sum(A′)\text{sum}(A)=\text{sum}(A\cap B)+\text{sum}(A')、sum(B)=sum(A∩B)+sum(B′)\text{sum}(B)=\text{sum}(A\cap B)+\text{sum}(B') であり、かつ sum(A)=sum(B)\text{sum}(A)=\text{sum}(B) であるから、両辺から共通項 sum(A∩B)\text{sum}(A\cap B) を引くと sum(A′)=sum(B′)\text{sum}(A')=\text{sum}(B') を得る。したがって A′A' と B′B' は、もとの10個の2桁の数からなる、互いに素で空でない2つの部分集合であり、和が等しい。これが求めるものである。