Problem 106

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) \neq S (C)$ ; that is, sums of subsets cannot be equal.
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?

NOTE: This problem is related to Problem 103 and Problem 105.

特殊的子集和：元检验

记 $S (A)$ 是大小为 $n$ 的集合 $A$ 中所有元素的和。若任取 $A$ 的任意两个非空且不相交的子集 $B$ 和 $C$ 都满足下列条件，我们称 $A$ 是一个特殊的和集：

$S (B) \neq S (C)$ ；也就是说，任意子集的和不相同。
如果 $B$ 中的元素比 $C$ 多，则 $S (B) > S (C)$ 。

在这个问题中我们假定集合中包含有 $n$ 个严格单调递增的元素，并且已知其满足第二个条件。

令人惊奇的是，当 $n = 4$ 时，在所有可能的 $25$ 组子集对中只有 $1$ 组需要检验子集和是否相等（第一个条件）。同样地，当 $n = 7$ 时，在所有可能的 $966$ 组子集对中只有 $70$ 组需要检验。

当 $n = 12$ 时，在所有可能的 $261625$ 组子集对中有多少组需要检验？

注意：此题和第103题及第105题有关。