百科问答小站 logo
百科问答小站 font logo



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

  

user avatar   liu-yang-zhou-23 网友的相关建议: 
      

一、某些尝试性的构造

上界

使用二进制表示,则

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

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

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

构造

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

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

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

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

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


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

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

    表示这个数至少需要四项。通过穷举,小于 的数都不满足题意。

于是我们猜测有规律:

证明

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

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

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


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


优化

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

证明

证明过程直接照搬:

于是得到:

通项公式

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

特征方程

于是通解为

其中 为待定系数。

所以上界下降为 (这是我的生日^-^)


二、整数规划

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

根据题目列出数学模型:

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

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

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

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




  

相关话题

  伽罗华并没有接受完整的数学教育,为何能解决当时最难的数学问题? 
  专业的数学爱好者喜欢的是数学的什么(请看问题描述)? 
  对于那些不会做的题,答案看懂了,思路记住了就够了吗? 
  如何评价一些数学大佬在推导过程中的「我们不难发现…」、「显然有…」、「易得…」等语言? 
  如何看待中国数学竞赛落败引网民狂欢? 
  2 的 100 次方到底有多大? 
  有哪些数学定理或者数学知识惊呆了你? 
  可测集多还是不可测集多? 即一维,直到n维的欧氏空间中,可测集类和不可测集类是否等势? 
  马云说「数学是一切的基础,数学好的人要尊重其他行业,基础学科只有变成应用才能真正发挥作用」,你同意吗? 
  什么情况下被积函数的原函数不能用初等函数表示?怎么判断呢? 

前一个讨论
N个互异数随机组成的数组的逆序数的分布公式是什么?
下一个讨论
你如何用八个字来形容逝去的爱情?





© 2025-05-06 - tinynew.org. All Rights Reserved.
© 2025-05-06 - tinynew.org. 保留所有权利