組合學/舒爾定理

舒爾定理指出，對於任何正整數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即可完成證明。