论坛 › 难题征解 › 100内,寻找一个集合A,元素全是自然数,得两两相加能表示2以上100以内所有的数？

无心人 发表于 2008-12-25 20:38:49

显然
0, 1, 2是必须的
使用0, 1, 2能表示的是0, 1, 2, 3
第一个不能表示的是4，加入
然后可以表示4, 5, 6
同样道理加入7

可以证明
序列 + 能达到要求

northwolves 发表于 2008-12-25 20:50:20

原帖由 xiugakei 于 2008-12-25 19:36 发表 http://bbs.emath.ac.cn/images/common/back.gif
我的估算是100内,只需要20个（10*2）左右
推广之后是
n只需要1.5*√n~2*√n个。

理论上似乎是这样。但它是基于四进制的：

4^1   2个
4^2   6个
4^3   14个
4^4   30个
....
4^k    2^(k+1)-2 个

令n=4^k
n 内需要 2*sqrt(n)-2 个

无心人 发表于 2008-12-25 20:53:45

同样道理
+ 也能

northwolves 发表于 2008-12-25 20:53:48

事实上，从1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32, 34, 40, 42, 64, 65, 68, 69, 80, 81, 84, 85任取两个相加可求出128以内任意整数

无心人 发表于 2008-12-25 20:56:03

对m >= 3
得到
+ 能满足要求
此时总共需要的个数是
(N - 1) / m + (m - 1)

无心人 发表于 2008-12-25 20:58:25

此时可证明
如果(N - 1) / m + m - 1最小
需要m =

比如N = 100，则m = 9
此时需要99 / 9 + 9 - 1 = 11 + 8 = 19个

northwolves 发表于 2008-12-25 21:02:43

原帖由 无心人 于 2008-12-25 20:58 发表 http://bbs.emath.ac.cn/images/common/back.gif
此时可证明
如果(N - 1) / m + m - 1最小
需要m =

比如N = 100，则m = 9
此时需要99 / 9 + 9 - 1 = 11 + 8 = 19个

讲得很透彻，但问题是不让使用0

无心人 发表于 2008-12-25 21:02:58

这时的序列是
能表示的数字是
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,3
0,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,
57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83
,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107
,108,110,119,128,137,146,155,164,173,182,191]

无心人 发表于 2008-12-25 21:09:52

那都增加1就是了
呵呵
Prelude List> let c =

northwolves 发表于 2008-12-25 21:11:24

哦，忘了，前两天有人提到，0 似乎算是自然数了，谁给个权威的连接？

查看完整版本: 100内,寻找一个集合A,元素全是自然数,得两两相加能表示2以上100以内所有的数？