Введение
Теорема в теории Рамзи. Теорема Ван дер Вэрдена — теорема в области математики, называемой теорией Рамзи. Теорема Ван дер Вэрдена утверждает, что для любых заданных положительных целых чисел r и k существует такое число N, что если целые числа от 1 до N окрашены, каждое одним из r различных цветов, то найдется хотя бы k целых чисел в арифметической прогрессии, элементы которых имеют один и тот же цвет. Наименьшее такое N называется числом Ван дер Вэрдена W(r, k) и названо в честь голландского математика Б. Л. ван дер Вэрдена. Эта теорема была предложена Пьером Жозефом Анри Боде в 1921 году. Ван дер Вэрден узнал о ней в 1926 году и опубликовал свое доказательство в 1927 году под названием «Доказательство гипотезы Боде» (Beweis einer Baudetschen Vermutung).
Van der Waerden's theorem is a theorem in the branch of mathematics called Ramsey theory. Van der Waerden's theorem states that for any given positive integers r and k, there is some number N such that if the integers {1, 2, , N} are colored, each with one of r different colors, then there are at least k integers in arithmetic progression whose elements are of the same color. The least such N is the Van der Waerden number W(r, k), named after the Dutch mathematician B. L. van der Waerden. This was conjectured by Pierre Joseph Henry Baudet in 1921. Waerden heard of it in 1926 and published his proof in 1927, titled Beweis einer Baudetschen Vermutung [Proof of Baudet's conjecture].
Доказательство теоремы Ван дер Вэрдена (в особом случае)
Следующее доказательство принадлежит Рону Грэму, Б. Л. Ротшильду и Джоэлю Спенсеру. Хинчин приводит довольно простое доказательство теоремы, не оценивая W(r, k).
Доказательство в общем случае
Доказательство для W(2, 3) по существу зависит от доказательства того, что W(32, 2) ≤ 33. Мы делим целые числа {1, …, 325} на 65 «блоков», каждый из которых можно раскрасить 32 различными способами, а затем показываем, что два блока из первых 33 должны быть одного цвета, и существует блок, раскрашенный в противоположный цвет. Аналогично, доказательство для W(3, 3) зависит от доказательства того, что…
Путем двойной индукции по числу цветов и длине прогрессии теорема доказывается в общем случае.
Эргодическая теория
Фурстенберг и Вайсс доказали эквивалентную форму теоремы в 1978 году, используя эргодическую теорию. Доказательство вышеуказанной теоремы тонкое, и читателю рекомендуется обратиться к [соответствующему источнику]. С помощью этой теоремы о возвратах теорему ван дер Вэрдена можно доказать в эргодико-теоретическом стиле.