选数字

northwolves

在$1-10^8$范围内选出$N$个数字,使其两两之和互不相等.
$N$最大值是多少?

7069

数学星空

由于每两个数的和均不相同,则N个数可构成$N*(N-1)/2$个不同的数,
因其最大值为$10^8+10^8-1$,最小值为3,则有
$N*(N-1)/2<=2*10^8-3$得:$N<=20000$

KeyTo9_Fans

楼上给的上界太大了吧？

我列了最小的几个数：

1,2,3,5,8,13,21,30

然后搜了一下，果然有这个数列！

https://oeis.org/search?q=2%2C3% ... glish&go=Search

与楼主的说法完全相同。

litaoye

可以用斐波那契求个下界。记得以前好像讨论过100以内的。

KeyTo9_Fans

楼上给的下界太小了吧？

不是斐波那契数列，虽然前几项看起来很像。

这里已经给出了N=2024的解：

http://www.research.att.com/~njas/sequences/b011185.txt

这里虽然条件更严格

http://www.research.att.com/~njas/sequences/A005282

但得到的解反而比前面的大：

N=2025

http://www.research.att.com/~njas/sequences/b005282.txt

gxqcn

主题帖里暗藏有秘密，不过现在不能告诉你。

mathe

上面给出的这些结果都不够好.
任意选择一个素数p使得$(p-1)p<10^8$

对于$[0,(p-1)p]$的整数根据其关于模p-1和p的余数可以看成二维空间$(x,y)$中的整数点,其中$0<=x<p-1,0<=y<p$,取p的原根g,取点列$(i,g^i(mod p)),0<=i<p-1$,映射回去,可以得到一个p-1个数的例子

northwolves

楼上给的下界太小了吧？

不是斐波那契数列，虽然前几项看起来很像。

这里已经给出了N=2024的解：

http://www.research.att.com/~njas/sequences/b011185.txt

这里虽然条件更严格

http://www.research ...
KeyTo9_Fans 发表于 2010-1-23 22:28

这个连接与我的题目相似但不完全相同

mathe

7#中方法选择p=9973就可以得到一个有9972个数的方案
而题目中如果允许两两之和中的"两两"为同一个数,那么就正好是Optimal Golomb Ruler (http://www.research.att.com/~njas/sequences/A003022)
http://topic.csdn.net/t/20020811/00/931488.html

northwolves

先降低难度: 如果在1-10000间取数,N最大多少?取哪些数字?