Special Subset Sums: Meta-testing

Let $S(A)$ represent the sum of elements in set $A$ of size $n$. We shall call it a special sum set if for any two non-empty disjoint subsets, $B$ and $C$, the following properties are true:
$S(B) \ne S(C)$; that is, sums of subsets cannot be equal.
If $B$ contains more elements than $C$ then $S(B) \gt S(C)$.
For this problem we shall assume that a given set contains $n$ strictly increasing elements and it already satisfies the second rule.
Surprisingly, out of the $25$ possible subset pairs that can be obtained from a set for which $n = 4$, only $1$ of these pairs need to be tested for equality (first rule). Similarly, when $n = 7$, only $70$ out of the $966$ subset pairs need to be tested.
For $n = 12$, how many of the $261625$ subset pairs that can be obtained need to be tested for equality?
NOTE: This problem is related to Problem 103 and Problem 105.

This problem comes from combinatorics and it’s crucial to understand that it’s talking about pairs of subsets, with each subset coming from a unique set of size $n$.

Since we’re talking about pairs of subsets, that means we are taking two subsets from the set. Therefore, we’ll use the combinations formula to generate pairs of subsets. The combinations formula is $\binom{n}{k}$ = $n$! / [$k$! * (n – $k$)!], where $n$ is the number of total elements and $k$ is the number of elements to choose.

To compute theoretical total subset pairs for a set of size $n$, we compute the number of non-empty subsets ($2^n – 1$), square it, and then divide by $2$ (since ordering doesn’t matter in subsets, we avoid double counting).

So,
Number of total subset pairs = [($2^n – 1$)^2] / 2

The second part is to figure out which pairs of subsets actually need to be tested for the “summation” equality requirement.

Here is the key point: For a given set of size $n$, to avoid “summation” equality, we only need to test the subset pairs which have the same subset size. Because bigger set has larger summation due to the initial condition in the problem, subset pairs with unequal subset size can be automatically deemed “safe” (namely, they satisfy the $S(B) > S(C)$ requirement).

So we only need to consider subset pairs having exactly the same subset sizes. For subset size $k$, we can choose $k$ elements out of $n$ in $\binom{n}{k}$ ways (combinations), and again half them due to no ordering.

Therefore,
Number of subset pairs that need to be tested = \[\sum_{k=1}^{n} (\binom{n}{k})^2 / 2\].

Comparing these two formulas, you will see why for $n=4$ and $n=7$, only $1$/$25$ and $70$/$966$ cases need to be tested, respectively.

For $n=12$, when using the above formula, you will find the answer is $32775$, namely, only $32775$ out of $261625$ subset pairs need to be tested for equality.

Final answer: $32775$ subset pairs need to be tested for $n=12$.

More Answers: