组合学/舒尔定理

舒尔定理指出，对于任何正整数r，存在一个正整数S，使得对于集合{1, ..., S}中整数的任何分成r个部分的划分，其中一个部分包含满足以下关系的整数x，y和z：

x + y = z。

证明：令n = R(3, ..., 3)，其中R(3, ..., 3) 表示r种颜色上的拉姆齐数。现在取S为n，并将集合{1, ..., n}中的整数划分成r个部分，我们用颜色来表示它们。也就是说，第一个部分中的整数被称为颜色c₁，第二个部分中的整数被称为颜色c₂，以此类推，直到颜色c_r。我们也可以说{1, ..., S}已被r-染色。这种术语在拉姆齐理论中很常见。

现在，我们对K_n的边进行染色，方法如下：边xy（表示连接顶点x和y的边）被赋予颜色c，如果|x - y|在划分中被染成颜色c。现在K_n一定包含一个单色三角形，假设它由顶点i > j> k构成。假设该三角形被染成颜色c_m。现在i - j，i - k和j - k也将被染成颜色c_m，即它们属于划分中的同一部分。只需取x = i - j，y = j - k和z = i - k即可完成证明。