Question

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

Answer 1

只需要构造一个 {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 <= 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

Answer 2

由{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

Answer 3

不会呀！

Answer 4

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