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

mathe

原帖由 gxqcn 于 2008-12-25 21:21 发表


新教材已把“0”归为自然数了，
所以为保险起见，我都改口用“正整数”来代替先前的“自然数”了。

通常欧美的教材将“0”归为自然数，俄国的“0”不算自然数。
我们过去一贯沿用俄国的习惯。
不过通常数学系教材里面不会使用自然数，而只使用正整数，非负整数来代替。

litaoye

不是费伯纳妾的问题呀！那么以Sqrt(n) = m 分段可以求出一组解，(1-m)(m * 2 - m * m)

不过不知道是不是最优的，没证明过。平均每个数都被用了m+1次，应该说效率已经很高了。

理论上要覆盖100个数，那么至少需要15个数C(15,2) = 105 > 100。（每个数都需要用13-14次）
但真想达到这样的效率，那怎么也得要费伯纳妾了，

to：northwolves  欧拉娶妻是什么问题？欧拉娶妻若干，数头10个，数腿18条......

xiugakei

无心人的[1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90]
应该就是答案了，和我的猜测一样，
n里面最多只需要2*√n个
只需要1，2，3....√n，2√n，.....这几个

无心人

现在缺个这就是最优化方案的证明

northwolves

对于 n=16,穷举找到16种方案：
1  2  3  4  8  11
1  2  3  4  8  12
1  2  3  5  7  8
1  2  3  6  7  8
1  2  3  6  7  9
1  2  3  6  8  12
1  2  4  5  7  8
1  2  4  5  7  11
1  2  4  5  8  10
1  2  4  5  9  11
1  2  4  5  10  11
1  2  4  5  10  12
1  2  4  6  7  8
1  2  4  6  7  9
1  2  4  6  7  14
1  2  4  6  8  9

northwolves

集合的最大元素最小：
n=2: 1
n=3: 1 2
n=4: 1 2
n=5: 1 2 3
n=6: 1 2 3
n=7: 1 2 3 4
n=8: 1 2 3 4
n=9: 1 2 4 5
n=10: 1 2 4 5
n=11: 1 2 3 5 6
n=12: 1 2 3 5 6
n=13: 1 2 4 6 7
n=14: 1 2 4 6 7
n=15: 1 2 3 5 7 8
n=16: 1 2 3 5 7 8
n=17: 1 2 4 6 8 9
n=18: 1 2 4 6 8 9
n=19: 1 2 4 5 7 9 10
n=20: 1 2 3 5 7 9 10
n=21: 1 2 3 6 9 10 11
n=22: 1 2 3 6 9 10 11
n=23: 1 2 3 4 5 7 9 11 12
n=24: 1 2 3 4 5 7 9 11 12
n=25: 1 2 3 4 5 8 11 12 13
n=26: 1 2 3 4 5 8 11 12 13
n=27: 1 2 3 4 5 10 11 13 14
n=28: 1 2 3 4 5 10 11 13 14
n=29: 1 2 3 4 7 10 13 14 15
n=30: 1 2 3 4 7 10 13 14 15
n=31: 1 2 3 5 8 11 14 15 16
n=32: 1 2 3 5 8 11 14 15 16
n=33: 1 2 3 6 9 12 15 16 17
n=34: 1 2 3 6 9 12 15 16 17
n=35: 1 2 3 4 7 9 14 15 17 18
n=36: 1 2 3 4 7 9 14 15 17 18
n=37: 1 2 3 4 8 12 14 17 18 19
n=38: 1 2 3 4 8 12 14 17 18 19
n=39: 1 2 3 6 9 12 15 18 19 20
n=40: 1 2 3 6 9 12 15 18 19 20
n=41: 1 2 4 5 10 12 17 18 20 21
n=42: 1 2 4 5 10 12 17 18 20 21
n=43: 1 2 3 4 7 11 15 17 20 21 22
n=44: 1 2 3 4 7 11 15 17 20 21 22
n=45: 1 2 3 4 8 12 16 18 21 22 23
n=46: 1 2 3 4 8 12 16 18 21 22 23
n=47: 1 2 3 4 5 8 13 15 20 21 23 24
n=48: 1 2 3 4 5 8 13 15 20 21 23 24
n=49: 1 2 3 4 5 9 14 16 21 22 24 25
n=50: 1 2 3 4 5 9 14 16 21 22 24 25
n=51: 1 2 3 4 5 10 15 17 22 23 25 26
n=52: 1 2 3 4 5 10 15 17 22 23 25 26
n=53: 1  2  3  4  5  6  11  16  18  23  24  26  27
n=54: 1  2  3  4  5  6  11  16  18  23  24  26  27
n=55: 1  2  3  4  5  7  12  17  19  24  25  27  28
n=56: 1  2  3  4  5  7  12  17  19  24  25  27  28
n=57: 1  2  3  4  5  9  13  18  20  25  26  28  29
n=58: 1  2  3  4  5  9  13  18  20  25  26  28  29

无心人

可以说
最小集合元素数是无法突破了

xiugakei

北方狼的结果是手算的还是计算机算的？
你前面找到的那些数列我仔细看了，
发现数列上2的n次方（n=1，2，3....）全部都在里面，而且他的结论更加方便于推广，在足够大的数，他的结果也更加优。可以只有数字没有公式。
还发现了4-8之间有2个数，8-16之间有2个数，16-32之间有4个数，32-64之间有4个数，64-128之间有8个数，128-256之间有8个数，256-512之间有16个数.....
2，2，4，4，8，8，16，16...明显有规律性

xiugakei

0, 1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32, 34, 40, 42, 64, 65, 68, 69, 80, 81, 84, 85, 128, 130, 136, 138, 160, 162, 168, 170, 256, 257, 260, 261, 272, 273, 276, 277, 320, 321, 324, 325, 336, 337, 340, 341, 512, 514, 520, 522, 544, 546, 552, 554, 640, 642, 648, 650

http://www.research.att.com/~njas/sequences/A126684
贴出来大家看