Problem 1

Prove that from a set of ten distinct two-digit numbers (in the decimal system), it is possible to select two disjoint subsets whose members have the same sum.

Step 3 of 4: Remove the common part to get disjoint sets

Previous step Next step

In plain words

Two different piles with the same total weight cannot be nested inside one another (once every item has positive weight), so after discarding the items they share, something is still left on each side.

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

Detailed analysis

Let $A'=A\setminus B$ and $B'=B\setminus A$ . These two sets are disjoint by construction. Since the elements of $S$ are positive, $A\neq B$ forces $A\not\subseteq B$ and $B\not\subseteq A$ (otherwise the sums could not be equal, as a proper subset has a strictly smaller sum than a superset once all elements are positive). Hence both $A'$ and $B'$ are nonempty.