一道组合数学题（悬赏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^

一道组合数学题（悬赏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^
一道组合数学题（悬赏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：这就是原题，不是我自己改的。

一道组合数学题（悬赏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^
只需要构造一个 {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

正在学习组合数学。。。
听说考试很简单

不会呀！

由{Ai} 可以这么构造一个 {1，2，。。。，3S(n-1)-2} 的 n-划分:
Bi = {3a, 3a-1 | a 属于 Ai}, i= 1,..., n-1
C = {3a-2| a <= S(n-1) }.
验证 没有x+y=z的解:
在C中， x+y 模3余2， z模3余1, 无解。
在Bi中， 观察 x,y 的形式有三类
1.如果有...

全部展开

由{Ai} 可以这么构造一个 {1，2，。。。，3S(n-1)-2} 的 n-划分:
Bi = {3a, 3a-1 | a 属于 Ai}, i= 1,..., n-1
C = {3a-2| a <= S(n-1) }.
验证 没有x+y=z的解:
在C中， x+y 模3余2， z模3余1, 无解。
在Bi中， 观察 x,y 的形式有三类
1.如果有 3a+3b = 3c 形式的解， 则 a+b=c 是原来的 Ai中的一个解，与Ai的条件矛盾。
2. (3a-1)+(3b-1) = 3(a+b)-2, 无解。
3. 如果有 3a+（3b-1） = 3c-1 形式的解，则 3b, 3c 也属于Bi, => 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

收起