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