上一篇:拉姆塞理论:舒尔数(一)

舒尔本人在他的 1916 年论文中提出一种递推构造:

设 [1, m] 可以分拆成 k 个无和集之并:

[1, m] = F1∪F2∪…∪Fk

则 [1, 3m+1] 可以分拆成 k+1 个无和集之并:

[1, 3m+1] = G1∪G2∪…∪Gk∪Gk+1

其中,对于 1≤i≤k,Gi = Fi∪(Fi + 2m + 1),

这里 Fi + 2m + 1 表示集 Fi 中各数都加上 2m + 1 后所得的集。

而 Gk+1 = [m+1, 2m+1]。

不难验证 G1, G2, …, Gk, Gk+1 都是无和集。

因此,从 [1, 4] 分拆成两个无和集之并 [1, 4] = {1,4} ∪ {2,3} 出发,按上述方法可把 [1, 13] 分拆成 3 个无和集之并:

[1, 13] = {1,4,10,13} ∪ {2,3,11,12} ∪ {5,6,7,8,9}。

这就证明了 S(3) ≥ 13 。

使用计算机容易证明 S(3) = 13,且 [1, 13] 只有 3 种方式分拆成 3 个无和集之并,另外两种如下:

[1, 13] = {1,4,10,13} ∪ {2,3,7,11,12} ∪ {5,6,8,9}

[1, 13] = {1,4,7,10,13} ∪ {2,3,11,12} ∪ {5,6,8,9}