0%

Problem 105


Problem 105


Special subset sums: 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 example, $\{81, 88, 75, 42, 87, 84, 86, 65\}$ is not a special sum set because $65 + 87 + 88 = 75 + 81 + 84$, whereas $\{157, 150, 164, 119, 79, 159, 161, 139, 158\}$ satisfies both rules for all possible subset pair combinations and $S(A) = 1286$.

Using sets.txt (right click and “Save Link/Target As…”), a 4K text file with one-hundred sets containing seven to twelve elements (the two examples given above are the first two sets in the file), identify all the special sum sets, $A_1, A_2, \ldots , A_k$, and find the value of $S(A_1) + S(A_2) +\ldots + S(A_k)$.

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


特殊的子集和:检验

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

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

例如,$\{81, 88, 75, 42, 87, 84, 86, 65\}$不是一个特殊和集,因为$65 + 87 + 88 = 75 + 81 + 84$,而$\{157, 150, 164, 119, 79, 159, 161, 139, 158\}$满足上述规则,且相应的$S(A) = 1286$。

在4K的文本文件sets.txt(右击并选择“目标另存为……”)中包含了一百组包含七至十二个元素的集合(文档中的前两个例子就是上述样例),找出其中所有的特殊和集$A_1, A_2, \ldots, A_k$,并求$S(A_1) + S(A_2) + \ldots + S(A_k)$的值。

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