一个数集的和是指它的所有元素之和．令 $S$ 是一些不超过15的正整数组成的集合，$S$ 的任意两个不相交的子集合的和不相等，并且在所有具有上述性质的集合中，$S$ 的和最大，求集合 $S$ 的和．
【难度】
【出处】
1986年第4届美国数学邀请赛（AIME）
【标注】
【答案】
61
【解析】
首先，$S$ 至多含有5个元素，因为若不然，$S$ 至少要有6个元素，其中元素不超过4的子集合至少要有 $\text{C}_{6}^{1}\text{+C}_{6}^{2}\text{+C}_{6}^{3}\text{+C}_{6}^{4}\text{=}56$ 个．
每个这种子集合的和至多为54（因为 $15\text{+}14\text{+}13\text{+}12\text{=}54$），由抽屉原理，至少有两个子集合的和相等．若这两个子集合不相交，则与“$S$ 的任意两个不相交的子集合的和不相等”的条件矛盾；若相交，去掉它们的公共元素之后同样将导致矛盾．因此 $S$ 至多含有5个元素．
下而来构造5元子集，使其元素尽可能地大．含15，14，13这后，$S$ 就不能含12（因为 $15+12=14+13$）．$S$ 可以含11．设 $S$ 含15，14，13，11之后，必不能含10与9（因 $10+15=14+11$，$9+5=13+11$），所以 $S$ 的第5个元素只能取8．不难验证，$S=\left\{ 8 , 11, 13, 14 ,15 \right\}$ 满足问题的条件，所以猜想 $8+11+13+14+15=61$ 是问题的解．
最后，证明最大值确实是61．如果能造出一个满足条件的集合 $S$，其和大于61，则 $S$ 必包含15，14，13（因为，即使不含其中最小者13，要想使和超过61，也必需含有10，11，12会产生 $15+11=14+12$，矛盾），从而 $S$ 不会含12．如果 $S$ 含11，则必导致上述和为61的集合，矛盾．如果 $S$ 不含11，那么即使 $S$ 含10与9也只能使其和达到 $15+14+13+10+9=61$，矛盾．所以61确实是最大值．
故集合 $S$ 的和为61．
每个这种子集合的和至多为54（因为 $15\text{+}14\text{+}13\text{+}12\text{=}54$），由抽屉原理，至少有两个子集合的和相等．若这两个子集合不相交，则与“$S$ 的任意两个不相交的子集合的和不相等”的条件矛盾；若相交，去掉它们的公共元素之后同样将导致矛盾．因此 $S$ 至多含有5个元素．
下而来构造5元子集，使其元素尽可能地大．含15，14，13这后，$S$ 就不能含12（因为 $15+12=14+13$）．$S$ 可以含11．设 $S$ 含15，14，13，11之后，必不能含10与9（因 $10+15=14+11$，$9+5=13+11$），所以 $S$ 的第5个元素只能取8．不难验证，$S=\left\{ 8 , 11, 13, 14 ,15 \right\}$ 满足问题的条件，所以猜想 $8+11+13+14+15=61$ 是问题的解．
最后，证明最大值确实是61．如果能造出一个满足条件的集合 $S$，其和大于61，则 $S$ 必包含15，14，13（因为，即使不含其中最小者13，要想使和超过61，也必需含有10，11，12会产生 $15+11=14+12$，矛盾），从而 $S$ 不会含12．如果 $S$ 含11，则必导致上述和为61的集合，矛盾．如果 $S$ 不含11，那么即使 $S$ 含10与9也只能使其和达到 $15+14+13+10+9=61$，矛盾．所以61确实是最大值．
故集合 $S$ 的和为61．
答案
解析
备注
