在编程中遇到的一个数论问题

sandwinds

问题描述:是否存在一个包含N个整数的集合，使其满足这样一个条件:从这个集合中选取两组任意相同个数个整数（假设一组为A，另一组为B ;则A交B为空），分别对着两组整数组求和，得到的两个结果始终不同。如果存在，是否存在多个，几个或无数个；那么又该用什么样的方法最快的列出符合前面条件的整数集？

希望各位数学界的DALAO们帮个忙，在此表示感谢！！

elim

先给一个极端的构造： M(n) = {a(1),.....,a(n)} 满足题设要求. 其中 a(1) = 1, a(2) = 2, a(n+2) = a(n+1) + a(n) +...+a(1).

这是一个组合论的好题. 盼望大家参与讨论.

sandwinds

elim 发表于 2018-8-5 21:41
先给一例： M(n) = {a(1),.....,a(n)} 满足题设要求. 其中 a(1) = 1, a(2) = 2, a(n+2) = a(n+1) + a(n).
...

这个可以把每一项都转换成以a1和a2来表示

sandwinds

elim 发表于 2018-8-5 21:41
先给一例： M(n) = {a(1),.....,a(n)} 满足题设要求. 其中 a(1) = 1, a(2) = 2, a(n+2) = a(n+1) + a(n).
...

楼主是什么工作

elim

二楼提出的数列是 Fibonacci (斐波那契）序列的一个极端化.  我其实还没有给出这么弄出来的集合满足楼主的要求的证明。这个证明也蛮有趣的。网友们试着证证？

elim

对不起我修改了构造方法。这使得相应的证明变得非常简单。

sandwinds

elim 发表于 2018-8-6 10:17
对不起我修改了构造方法。这使得相应的证明变得非常简单。

你是说，斐波那契数列，符合条件？

sandwinds

elim 发表于 2018-8-6 10:17
对不起我修改了构造方法。这使得相应的证明变得非常简单。

我列举出来3+5+8=1+2+13   强斐波那契是不符合的

elim

不再是Fibonacci 序列了，而是后一项是前面所有项的和．

Ysu2008

这个嘛，自然是有的啰。

注意看：1，2，4，8，16，32，...，2^n，...

这些数的二进制是这样的：
...0001
...0010
...0100
...1000
... ...

每个数只有1个“1”，且“1”的位置两两不同，犹如特征位置编码。可以用“逻辑或”把这些数加起来。
因为特征位置编码没有重复、不会移动，不难推知：任意两组数字相加的和相等的充要条件是两组数字一一对应相等。

32位 integer 有32个，64位 long 型有64个，如果嫌少就自定义数据结构啰。