Let A be a set if 3 distinct natural numbers, none of which exceeds 18.

Question

Let $A$ be a set of 3 distinct natural numbers, none of which exceeds $18$. Prove that the sums of the elements in all the nonempty subsets of $A$ are not distinct.

Can someone help me with this question ?

Thank you

Answer 1

There are $2^7=128$ subsets of $A=\{x_1,\dots,x_7\}\subseteq\mathbb{N}$, or not counting the empty set $127$ non-empty sets. Now, the maximal summation value for a non-empty subset is the value of the sum of $A$ itself. The largest such $A$ is given by $A=\{21,20,19,18,17,16,15\}$ (why?), i.e. for any such $A$, we now have $$x_1+\dots+x_7\leq21+20+19+18+17+16+15=126$$ as the values are all positive and distinct and don't exceed $21$, i.e.

For some $\varnothing\neq X\subseteq A$, denote the sum over its elements with $\sum X$.

Then, for every $\varnothing \neq X\subseteq A$, $\sum X\leq \sum A\leq 126$, again as they are all positive. Thus, for all $\varnothing\neq X\subseteq A$: $\sum X\leq 126$ but we have $127$ such distinct $X$, i.e. by the pigeonhole principle, we have that they can't be distinct.