Теорема Ван дер Вардена.

Значительная часть ранних исследований по теории Рамсея была посвящена множествам точек и линий, но всё же во многих из них рассматривались и множества чисел. Голландский математик Бартель Л.Ван дер Варден начал решать такие задачи ещё до того, как Рамсей доказал свою теорему.

В 1926 году Ван дер Варден встретился с интересной задачей, связанной с арифметическими прогрессиями. Как следует из самого названия, арифметическая прогрессия — это такая последовательность чисел, в которой разность между двумя соседними членами остаётся постоянной. Например, последовательность 3, 5, 7 есть трёхчленная арифметическая прогрессия, в которой разность между соседними членами равна двум. Частный случай задачи, привлёкшей внимание Ван дер Вардена, можно сформулировать так. Если каждое целое число от 1 до 9 напечатать на странице одной из двух красок, красной или синей, то всегда ли найдутся три синих или три красных числа, образующие арифметическую прогрессию? Ответ даётся в следующей врезке.

Теория Рамсея и арифметические прогрессии.

Арифметическая прогрессия — это последовательность чисел, в которой разность между соседними членами остаётся постоянной. Например, 7, 10, 13, 16 — это арифметическая прогрессия, в которой разность между соседними членами равна трём. Из теории Рамсея следует такое утверждение об арифметических прогрессиях: если каждое число от 1 до 9 покрасить в красный или синий цвет, то либо три синих числа, либо три красных образуют арифметическую прогрессию.

Чтобы доказать это утверждение, мы могли бы проверить все 512 способов раскраски девяти чисел. Но мы можем доказать его, рассмотрев только два случая. Начнём со случая, в котором 4 и 6 имеют одинаковый цвет, скажем синий.

1 2 3 4 5 6 7 8 9

Чтобы избежать синей арифметической прогрессии 4, 5, 6, мы покрасим 5 в красный цвет.

1 2 3 4 5 6 7 8 9

Чтобы избежать синих арифметических прогрессий 2, 4, 6 и 4, 6, 8, мы покрасим 2 и 8 в красный цвет.

1 2 3 4 5 6 7 8 9

Но тогда у нас получится красная арифметическая прогрессия 2, 5, 8. Итак, если 4 и 6 имеют одинаковый цвет, то всегда получится либо красная, либо синяя арифметическая прогрессия. Теперь рассмотрим случай, когда 4 и 6 имеют различный цвет. Число 5 можно покрасить как угодно, не создав при этом арифметической прогрессии, так что мы произвольно покрасим 5 в красный цвет.

1 2 3 4 5 6 7 8 9

Продолжим раскрашивание следующим образом:

3, чтобы избежать 3 4 5

9, чтобы избежать 3 6 9

7, чтобы избежать 5 7 9

8, чтобы избежать 6 7 8

2, чтобы избежать 2 5 8

1, чтобы избежать 1 2 3

Такое раскрашивание даёт последовательность

1 2 3 4 5 6 7 8 9

Но в ней всё равно осталась красная арифметическая прогрессия 1, 5, 9. Таким образом, независимо от того, в одинаковый или в разные цвета окрашены 4 и 6, всегда имеется либо синяя, либо красная арифметическая прогрессия.

Ван дер Варден поставил перед собой следующую задачу, являющуюся обобщением предыдущей: доказать, что если n — достаточно большое число и все целые числа от 1 до n напечатаны на странице одним из двух произвольно выбираемых для каждой цифры цветов, то всегда существует одноцветная последовательность с определённым числом членов, являющаяся арифметической прогрессией. Это утверждение можно считать теоремой Рамсея для арифметических последовательностей, хотя оно общеизвестно под названием теоремы Ван дер Вардена.

Ван дер Варден призвал на помощь своих коллег Эмиля Артина и Отто Шрейера. Позднее он писал: «Мы пришли в кабинет Артина на факультет математики Гамбургского университета и попытались найти доказательство. Мы рисовали на доске какие-то рисунки. У нас было состояние, которое немцы называют Einfälle (озарение), когда в голову приходят неожиданные идеи. Несколько раз такие новые идеи направляли обсуждение в новое русло, и одна из них в конце концов привела к решению». Оказалось, однако, что Ван дер Варден не смог доказать этот результат для двух красок, не доказав его для случая, когда одновременно используется произвольное число красок.

В своём доказательстве Ван дер Варден применил особый вид математической индукции. Обычная (одинарная) индукция включает в себя два этапа. На первом этапе нужно показать, что утверждение выполняется для некоторого малого числа, скажем, для двух. На втором этапе доказывается, что если утверждение справедливо для какого-либо числа, то оно справедливо и для числа, на единицу большего. Отсюда следует, что оно верно для трёх, четырёх и так далее. Результаты «идут в руки» один за другим как бесконечная очередь падающих костяшек домино, поставленных на ребро: если столкнуть одну, то упадут все.

Чтобы доказать теорему Рамсея для арифметических прогрессий, Ван дер Варден применил более тонкую, двойную индукцию. Он предположил, что для любого фиксированного числа красок существует число n, такое, что если каждое целое число в интервале от одного до n напечатать какой-нибудь из этих красок, то найдётся арифметическая прогрессия чисел одного цвета, состоящая, скажем, из 10 членов. Опираясь на это допущение, он смог показать, что для любого фиксированного набора красок существует число m, такое, что если каждое целое число в интервале от 1 до m напечатать какой-нибудь из этих красок, то будет существовать одноцветная арифметическая прогрессия из 11 членов. В общем, он показал, что из результатов для k членов и любого количества красок вытекает результат для k+1 членов и любого количества красок.