[Math] Let S be a set of six positive integers who maximum is at most 14.

discrete mathematics

Let $\mathcal S$ be a set of six positive integers who maximum is at most 14. Show that the sums of the elements in all the nonempty subsets of $\mathcal S$ cannot all be distinct

For each non-empty subset, $\mathcal A$ of $\mathcal S$ the sum of the elements in $\mathcal A$ denoted as $S_\mathcal A$ satisfies
$$1\leq S_\mathcal A \leq 9 + 10 + \cdots + 14 = 69$$
and there are $2^6−1=63$ non-empty subsets.

How do you know that the sums start from $9$ and goes to $14$? $(9+10+…+14= 69)$. Why can't it start from $1$?

Best Answer

Suppose $S$ contains two equal elements. Then the subsets of $S$ comprising only these elements have equal sums, so the sums are not all distinct.

Now suppose $S$ does not contain two equal elements, i.e. the elements of $S$ are all distinct.

Let $x$ be the smallest element of $S$.

Then the smallest possible value of $S_A$ is $x$.

And the largest possible value of $S_A$ is $x+10+11+12+13+14=x+60$.

Since $x<S_A<x+60$, there are $61$ possible values of $S_A$.

And since there are $2^6-1=63$ non-empty subsets, these cannot all have distinct sums since there are only $61$ possible values available for the sum.

Related Question