作业帮由n个正整数组成的集合,子集元素和两两不同,最大数的最小值记为k(n).容易有k(1)=1,k(2)=2,k(3)=4,k(4)=7,k(5)=13求证k(6)>=21,k(7)>=38,最好能求出为24,44.关于k(n),有怎样的结论?
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/29 07:44:09
由n个正整数组成的集合,子集元素和两两不同,最大数的最小值记为k(n).容易有k(1)=1,k(2)=2,k(3)=4,k(4)=7,k(5)=13求证k(6)>=21,k(7)>=38,最好能求出为24,44.关于k(n),有怎样的结论?
由n个正整数组成的集合,子集元素和两两不同,最大数的最小值记为k(n).
容易有k(1)=1,k(2)=2,k(3)=4,k(4)=7,k(5)=13
求证k(6)>=21,k(7)>=38,最好能求出为24,44.
关于k(n),有怎样的结论?
由n个正整数组成的集合,子集元素和两两不同,最大数的最小值记为k(n).容易有k(1)=1,k(2)=2,k(3)=4,k(4)=7,k(5)=13求证k(6)>=21,k(7)>=38,最好能求出为24,44.关于k(n),有怎样的结论?
这是个未解问题,我只知道有个 Conway–Guy 序列,是这个.
你可以搜索：Conway–Guy sequence,找到一些参考资料.
这个问题是这样：
最显然的答案就是2的幂次：1、2、4、8、16、32…… 它们的“子集元素和”两两不同.
Conway–Guy 序列并没有比这个小太多.
BTW：我在下面的参考资料里给了一个链接,希望百度不要吞了.
当n=1的时候**为{1} k（n）<=1
当n=2的时候**为{1,2} k（n）<=2
当n=3的时候**为{2,3,4} k（n）<=4
当n=4的时候**为{3,5,6,7} k（n）<=7
当n=p的时候有
{a1，a2，a3……，ap}
a1
a1+a2+a3>ap-1+ap<...
全部展开
当n=1的时候**为{1} k（n）<=1
当n=2的时候**为{1,2} k（n）<=2
当n=3的时候**为{2,3,4} k（n）<=4
当n=4的时候**为{3,5,6,7} k（n）<=7
当n=p的时候有
{a1，a2，a3……，ap}
a1
a1+a2+a3>ap-1+ap
……
满足题意 即子集元素和两两不同 此时有k(n)<=ap
因此 {a1+b，a2+b，a3+b……，ap+b} b>0
也满足
a1+b
a1+b+a2+b+a3+b>ap-1+b+ap+b
……
满足题意
因此对于{b，a1+b，a2+b，a3+b……，ap+b}
我们需要有
b+a1+b>ap+b
b+a1+b+a2+b>ap+b+ap-1+b
……
它也满足题意
n=4时 **{3,5,6,7}满足以上条件
因此**{b，3+b，5+b，6+b，7+b}
在b+3+b>7+b
b+3+b+5+b>6+b+7+b时也满足题意
即b+8>13 b>5
取b的最小值b=6
因此{6,9,11,12,13}满足题意 有k(5)<=13
对于**{b,6+b,9+b,11+b,12+b,13+b}
b+6+b+9+b>12+b+13+b时满足题意
即b+15>25 b>10
取b的最小值 b=11
因此**{11,17,20,22,23,24}满足题意 有k(6)<=24
对于**{b,11+b,17+b,20+b,22+b,23+b,24+b}
4b+11+17+20>22+23+24+3b
b+48>69 b>21 取b的最小值b=22
因此**{22,33,39,42,44,45,46}满足题意 有k（7）<=46
但这不是最优解 最优解是{20,31,37,40,42,43,44} 这边有点不大会证明了
收起