如何找到一个10项的非负整数数列，使该数列的任意不超过3项的和不重复，并使数列的最大项最小，并证明? 第1页

一、某些尝试性的构造

上界

使用二进制表示，则

那么对上面数列任意多项求和，所得到的集合：

因为求和的时候永远不会出现进位的情况，所以避免了重复的结果。

因此数列最大一项的上界不超过

构造

按照题意，数列不能出现相同的数字，否则若 ，这与题意相悖。现在尝试逐级构造该数列。

• 若从 开始：
  
• 若 ，就会有 ,与题意相悖，故有
  
• 若 ，就会有 ，矛盾。若 ，有 ，矛盾。若 ，有 ，矛盾。于是只有
  

我们用归纳法。假设前 项是 ，若 ，那么 的二进制表示为

这个数总可以被前面 项表示出来，即

题目要求不超过 项求和，所以这个推理可以在 得到保证，也就是说一直到 都是满足 的升幂规律。

但是接下来该怎么办？我们需要找到新的规律。

• 注意到 需要四个 表示，而 中其余的数字仅需要不超过三个 就能表示。假设 ，那么凡是涉及 的求和总是不小于其余不超过三项的求和，所以满足题意，
  
• 那么我们再寻找下一个这样的数：
  
  表示这个数至少需要四项。通过穷举，小于 的数都不满足题意。
  

于是我们猜测有规律：

证明

归纳法。假设 对 皆成立，于是下面证明 是满足题意的整数。

同前文推理，凡涉及 的和，总有

所以 不超过三项求和的结果总是不一样的。于是我们得到新的上界 。

至于这个界是否最小，我还没有想到巧妙的证明方法。暴力穷举当然也是可以的了……

优化

感谢评论区的网友@simplex3 提示，只需将改一改，就能得到更小的上界：

证明

证明过程直接照搬：

于是得到：

通项公式

我们求一下非齐次线性递推方程 的通项公式：

特征方程

于是通解为

其中 为待定系数。

所以上界下降为 （这是我的生日^-^）

二、整数规划

这是一个整数规划的问题。

根据题目列出数学模型：

这究竟有多少个不等式呢？由排列组合可知：

对于 而言，代入计算得 个不等式。（看来这个问题注定非人力可以解决。）

对于这类问题一般选用割平面法、分支定界法。

这个问题……计算机也得累死。