百度作业网一道组合数学题（悬赏50分）
来源：学生作业帮 编辑：百度作业网作业帮 分类：数学作业 时间：2024/04/30 08:43:17
一道组合数学题（悬赏50分）
设Sn是满足下列条件的最小整数：把{1,2,.,Sn}划分成n个子集,总存在一个子集,其中有x+y=z的解,证明：
（1）S1=2；
（2）S2=5；
（3）S3=14；
（4）Sn>=3S(n-1)-1；
（5）Sn>=1/2(3^n+1).
回答者只要能证明出（4）即可,如果证不出（4）能根据证明（1）-（3）给出一定的启示思路也有可能给分.如果步骤写的好,会酌情提高悬赏分（已经有50分的悬赏了,也就是说还会加）.不会的请不要来瞎凑热闹了.
这个题应该要用到推广的Ramsey数,也就是Rn=R（3,3,…,3）的性质.
补充：问题出处为中科大所编的《组合数学》教材最新版第一章习题。
回复4L：这就是原题，不是我自己改的。
设Sn是满足下列条件的最小整数：把{1,2,.,Sn}划分成n个子集,总存在一个子集,其中有x+y=z的解,证明：
（1）S1=2；
（2）S2=5；
（3）S3=14；
（4）Sn>=3S(n-1)-1；
（5）Sn>=1/2(3^n+1).
回答者只要能证明出（4）即可,如果证不出（4）能根据证明（1）-（3）给出一定的启示思路也有可能给分.如果步骤写的好,会酌情提高悬赏分（已经有50分的悬赏了,也就是说还会加）.不会的请不要来瞎凑热闹了.
这个题应该要用到推广的Ramsey数,也就是Rn=R（3,3,…,3）的性质.
补充：问题出处为中科大所编的《组合数学》教材最新版第一章习题。
回复4L：这就是原题，不是我自己改的。
只需要构造一个 {1,2,.,3S(n-1)-2} 的 n-划分, 使得划分中的任何子集都没有x+y=z的解.
存在 {1,2,.,S(n-1)-1} 的 （n-1）-划分： A1,A2, ...,A(n-1), 使得划分中的任何子集都没有x+y=z的解.
由{Ai} 可以这么构造一个 {1,2,.,3S(n-1)-2} 的 n-划分:
Bi = {3a, 3a-1 | a 属于 Ai}, i= 1,..., n-1
C = {3a-2| a a+b=c 是原来的 Ai中的一个解,与Ai的条件矛盾.
所以 {1,2,.,3S(n-1)-2} 的 n-划分,B1,.,B（n-1）,C 使得划分中的任何子集都没有x+y=z的解.所以 Sn>=3S(n-1)-1
存在 {1,2,.,S(n-1)-1} 的 （n-1）-划分： A1,A2, ...,A(n-1), 使得划分中的任何子集都没有x+y=z的解.
由{Ai} 可以这么构造一个 {1,2,.,3S(n-1)-2} 的 n-划分:
Bi = {3a, 3a-1 | a 属于 Ai}, i= 1,..., n-1
C = {3a-2| a a+b=c 是原来的 Ai中的一个解,与Ai的条件矛盾.
所以 {1,2,.,3S(n-1)-2} 的 n-划分,B1,.,B（n-1）,C 使得划分中的任何子集都没有x+y=z的解.所以 Sn>=3S(n-1)-1