Problem 103

Special Subset Sums: Optimum

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)$ .

If $S (A)$ is minimised for a given $n$ , we shall call it an optimum special sum set. The first five optimum special sum sets are given below.

$\begin{aligned} n = 1 : & {1} \\ n = 2 : & {1, 2} \\ n = 3 : & {2, 3, 4} \\ n = 4 : & {3, 5, 6, 7} \\ n = 5 : & {6, 9, 11, 12, 13} \end{aligned}$

It seems that for a given optimum set, $A = {a_{1}, a_{2}, \dots, a_{n}}$ , the next optimum set is of the form $B = {b, a_{1} + b, a_{2} + b, \dots, a_{n} + b}$ , where $b$ is the “middle” element on the previous row.

By applying this “rule” we would expect the optimum set for $n = 6$ to be $A = {11, 17, 20, 22, 23, 24}$ , with $S (A) = 117$ . However, this is not the optimum set, as we have merely applied an algorithm to provide a near optimum set. The optimum set for $n = 6$ is $A = {11, 18, 19, 20, 22, 25}$ , with $S (A) = 115$ and corresponding set string: $111819202225$ .

Given that $A$ is an optimum special sum set for $n = 7$ , find its set string.

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

特殊的子集和：最优解

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

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

对于给定的 $n$ ，称使得 $S (A)$ 最小的集合 $A$ 为最优特殊和集。前 $5$ 个最优特殊和集如下所示。

$\begin{aligned} n = 1 : & {1} \\ n = 2 : & {1, 2} \\ n = 3 : & {2, 3, 4} \\ n = 4 : & {3, 5, 6, 7} \\ n = 5 : & {6, 9, 11, 12, 13} \end{aligned}$

似乎对于一个给定的最优特殊和集 $A = {a_{1}, a_{2}, \dots, a_{n}}$ ，下一个最优特殊和集将是 $B = {b, a_{1} + b, a_{2} + b, \dots, a_{n} + b}$ ，其中 $b$ 是位于集合 $A$ “中间”位置的元素。

应用这条“规则”，我们猜测对于 $n = 6$ 的最优特殊和集将是 $A = {11, 17, 20, 22, 23, 24}$ ，相应的 $S (A) = 117$ 。然而事实并非如此，上述“规则”仅仅只能给出近似最优解。对于 $n = 6$ ，最优特殊和集是 $A = {11, 18, 19, 20, 22, 25}$ ，其相应的 $S (A) = 115$ ，并可以表示为数字字符串： $111819202225$ 。

求 $n = 7$ 时的最优特殊和集 $A$ ，并给出其数字字符串表示。

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