数学研发论坛

 找回密码
 欢迎注册
查看: 6255|回复: 36

[讨论] 选数字

[复制链接]
发表于 2010-1-23 19:48:48 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

7069
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-23 20:18:54 | 显示全部楼层
由于每两个数的和均不相同,则N个数可构成$N*(N-1)/2$个不同的数,
因其最大值为$10^8+10^8-1$,最小值为3,则有
$N*(N-1)/2<=2*10^8-3$得:$N<=20000$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-23 21:54:51 | 显示全部楼层
楼上给的上界太大了吧?

我列了最小的几个数:

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

然后搜了一下,果然有这个数列!

http://www.research.att.com/~nja ... mp;language=english

与楼主的说法完全相同。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-23 22:23:33 | 显示全部楼层
可以用斐波那契求个下界。记得以前好像讨论过100以内的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-23 22:28:49 | 显示全部楼层
楼上给的下界太小了吧?

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

这里已经给出了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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-24 08:25:59 | 显示全部楼层
主题帖里暗藏有秘密,不过现在不能告诉你。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-24 11:58:44 | 显示全部楼层
上面给出的这些结果都不够好.
任意选择一个素数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个数的例子

评分

参与人数 1鲜花 +1 收起 理由
KeyTo9_Fans + 1 不错的方法。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-1-24 13:28:48 | 显示全部楼层
楼上给的下界太小了吧?

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

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

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

这里虽然条件更严格

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


这个连接与我的题目相似但不完全相同
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-24 14:51:29 | 显示全部楼层
7#中方法选择p=9973就可以得到一个有9972个数的方案
而题目中如果允许两两之和中的"两两"为同一个数,那么就正好是Optimal Golomb Ruler (http://www.research.att.com/~njas/sequences/A003022)
http://topic.csdn.net/t/20020811/00/931488.html
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-1-24 15:14:23 | 显示全部楼层
先降低难度: 如果在1-10000间取数,N最大多少?取哪些数字?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2018-9-20 00:34 , Processed in 0.137434 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表