Subsets with a Unique Sum

For any set $A$ of numbers, let $\operatorname{sum}(A)$ be the sum of the elements of $A$.
Consider the set $B = \{1,3,6,8,10,11\}$. There are $20$ subsets of $B$ containing three elements, and their sums are:

\begin{align}
\operatorname{sum}(\{1,3,6\}) &= 10,\\
\operatorname{sum}(\{1,3,8\}) &= 12,\\
\operatorname{sum}(\{1,3,10\}) &= 14,\\
\operatorname{sum}(\{1,3,11\}) &= 15,\\
\operatorname{sum}(\{1,6,8\}) &= 15,\\
\operatorname{sum}(\{1,6,10\}) &= 17,\\
\operatorname{sum}(\{1,6,11\}) &= 18,\\
\operatorname{sum}(\{1,8,10\}) &= 19,\\
\operatorname{sum}(\{1,8,11\}) &= 20,\\
\operatorname{sum}(\{1,10,11\}) &= 22,\\
\operatorname{sum}(\{3,6,8\}) &= 17,\\
\operatorname{sum}(\{3,6,10\}) &= 19,\\
\operatorname{sum}(\{3,6,11\}) &= 20,\\
\operatorname{sum}(\{3,8,10\}) &= 21,\\
\operatorname{sum}(\{3,8,11\}) &= 22,\\
\operatorname{sum}(\{3,10,11\}) &= 24,\\
\operatorname{sum}(\{6,8,10\}) &= 24,\\
\operatorname{sum}(\{6,8,11\}) &= 25,\\
\operatorname{sum}(\{6,10,11\}) &= 27,\\
\operatorname{sum}(\{8,10,11\}) &= 29.
\end{align}

Some of these sums occur more than once, others are unique.
For a set $A$, let $U(A,k)$ be the set of unique sums of $k$-element subsets of $A$, in our example we find $U(B,3) = \{10,12,14,18,21,25,27,29\}$ and $\operatorname{sum}(U(B,3)) = 156$.
Now consider the $100$-element set $S = \{1^2, 2^2, \dots, 100^2\}$.
S has $100891344545564193334812497256$ $50$-element subsets.
Determine the sum of all integers which are the sum of exactly one of the $50$-element subsets of $S$, i.e. find $\operatorname{sum}(U(S,50))$.

This problem sounds complicated at first, but we can break it down using simple mathematical principles.

$S$ is a set of squares ranging from $1 \text{ to } 100^2$, and we’re interested in the subset sums where each subset contains 50 elements.

For a set of size n, there are overall $\binom{n}{k}$ ways to select k elements. So in our situation, there are $\binom{100}{50}$ 50-elements subsets.

We know that any subset sum will end up in the range $50 \times 1^2 (=50)$ to $50 \times 100^2(=5000)$.

In order to make each subset sum unique, we need to ensure there are more subset sums than the number of possible values in this range.

¥ The amount of possible subset sums is $\binom{100}{50}$.

¥ The amount of possible values in our range is $5000 – 50 + 1 = 4951$.

So, we can conclude that there will be repeated values; there are many more possible 50-element subsets than there are possible sums in the given range.

This necessarily means that it’s impossible for all the sums to be unique, and as such, $U(S, 50)$ is an empty set ($U(S, 50) = \emptyset$).

Hence, $\operatorname{sum}(U(S,50)) = 0$. This means the sum of all integers, which are the sum of exactly one of the 50-element subsets of S, is 0.

More Answers: