Mfcttrf

Consider the problem below:

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:

1. $S(B) ≠ S(C)$; that is, sums of subsets cannot be equal.




2. If $B$ contains more elements than $C$ then $S(B) > 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?

My question is why for $n=4$ there are $25$ possible subset pairs? If my calculations are correct, then the number must equal $21$.

My logic is following:

Note: I'm not mathematician, so I am not sure whether term "length of set" exists in math, so just to make sure, "length of the set" below refers to the number of elements that the set contains (e.g. length of $2,3,4$ will equal $3$)

1. The problem specifies that if lengths of two subsets are not equal, subset with larger length will have larger sum. Thus when testing set for equality, we only consider pairs of subsets with the SAME length.


2. Pairs of subsets with length 1 should be ignored, because each value in the set is unique.


3. Consider subsets with length 2. In total there are Combinations(4,2) = 6 subsets. For 6 subsets, there are Combinations(6,2) = 15 pairs that can be formed.


4. Consider subsets with length 3. In total there are Combinations(4,3) = 4 subsets. For 4 subsets, Combinations(4,2) = 6 pairs can be formed.


5. Because there is only one subset with length 4, thus no pairs can be formed.


6. Total = 15 + 6 = 21

Where did I make the mistake?

Each element of or $n$-element set $A$ has three possibilities: It can be element of $B$, or of $C$, or of neither. Therefore, we count $3^n$ ways of having two disjoint subsets $B,C$ of $A$. But $B$ must be non-empty; therefore we subtract the $2^n$ cases where $B=emptyset$ and $C$ is any of thge $2^n$ subsets of $A$. Likewise we subtract the $2^n $ cases where $C=emptyset$ and $B$ is any subset of $A$. Oops, we subtracted the case $B=C=emptyset$ twice, hence we must add it back in. So we count
$$tag13^n-2^n-2^n+1 $$
ways of picking disjoint non-empty subsets $B,C$ of $A$.
We are still overcounting insofar as we count ordered pairs of subsets. As swapping $B$ with $C$ does not really make a difference, we are interested in half of $(1)$, i.e., in
$$tag2 frac3^n+12-2^n$$
unordered pairs of disjoint non-empty subsets of $A$. For $n=4$, $(2)$ equals $frac81+12-16=25$.
This is the $25$ the problem statement is referring to. Note that this still counts pairs of different size (for which we need only check condition 2) and pairs of singleton sets (for which condition 1 as trivially true). In fact, for $A=a,b,c,d$ with $a<b<c<d$ we need only check $B=a,d$, $C=b,c$ if we already know that condition 2 holds. This is because for example $a+c<b+d$ follows already without explicit check from $a<b$ and $c<d$.

Explicitly, the list of subset pairs are

1,2
1,3
1,4
2,3
2,4
3,4
1,2,3
1,2,4
1,3,2
1,3,4
1,4,2
1,4,3
2,3,1
2,3,4
2,4,1
2,4,3
3,4,1
3,4,2
1,2,3,4
1,3,2,4
1,4,2,3
1,2,3,4
1,2,4,3
1,3,4,2
2,3,4,1

Note that we're counting pairs with different sizes here, and that many of the candidates your method created (such as 12 of the "15" pairs of size-2 subsets) aren't counted because they aren't disjoint.

As for checking equality, we need to check equality if: 1. the two subsets are the same cardinality, and 2. it is not true that the $n$th largest item in one particular subset is always larger than the $n$th largest item in the other: if all the winners are on one side, the other side can't possibly close the gap. Of the 90 subset pairs for sets of size 5, 15 have both subsets the same size and their sizes are larger than 1, and only 5 of those meet the ordering requirement that makes it possible to have them turn out equal: 1,4,2,3; 1,5,2,3; 1,5,2,4; 1,5,3,4; and 2,5,3,4.