0%

Problem 106


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:

  1. $S(B) \neq 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?

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


特殊的子集和:元检验

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

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

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

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

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

注意:此题和第103题第105题有关。