Реферат: Теория Рамсея
В 1926году Бартель Л. Ван дер Варден доказал, что если n — достаточно большое число и если все числа от 1 до n произвольным образом раскрасить каким-нибудь из двух цветов, то всегда найдётся одноцветная арифметическая прогрессия с определённым числом членов. В 1963году А.Хейлз и Р.Джуитт открыли то, что оказалось сутью теоремы Ван дер Вардена, изучая игру «крестики-нолики». Хотя классический вариант этой игры с игровым полем размером три на три может быстро наскучить, трёхмерный вариант с четырьмя полями в каждом ряду весьма интересен. «Доской» для трёхмерной игры служит куб, разбитый на 64 ячейки. Игроки по очереди заполняют ячейки крестиками или ноликами, пока один из них не выигрывает, заполнив четыре ячейки, расположенные на одной прямой. И двумерная, и трёхмерная игра порой кончается ничьей. А как обстоит дело в случае игр более высокой размерности? Можно ли гарантировать выигрыш в некотором n-мерном варианте крестиков и ноликов с k элементами на одной прямой?
Хейлз и Джуитт показали, что если размерность n достаточно велика, то всегда можно найти вариант игры с k элементами на одной прямой, который никогда не кончается ничьёй. Например, независимо от того, как расположены крестики и нолики в трёхмерной игре с тремя элементами в ряду, всегда либо три крестика будут расположены на одной прямой, либо три нолика.
Теорему Ван дер Вардена можно вывести из результата Хейлза и Джуитта, применив преобразование, переводящее прямые этой игры в арифметические прогрессии. Рассмотрим трёхмерную игру с тремя элементами в ряду.
Координаты крестиков в этой выигрышной комбинации суть 121, 222 и 323; рассматриваемые как числа, они образуют арифметическую прогрессию. Можно показать, что всякая выигрышная комбинация, преобразованная этим методом, даёт арифметическую прогрессию.
1
1
2 ×
3
1 2 3
2
1
2 ×
3
1 2 3
3
1
2 ×
3
1 2 3
Доказав теорему Рамсея для арифметических прогрессий, Ван дер Варден применил эти знания к решению следующей задачи. Каково наименьшее значение n, гарантирующее существование одноцветной арифметической последовательности из, скажем, 10 членов, если каждое число от 1 до n напечатать любой произвольно выбранной из двух красок? Лучший ответ, который Ван дер Варден смог найти, выражался столь большим числом, что его невозможно было записать в обычном виде. Оно было больше миллиарда, больше чем 10 в степени миллиард.
В самом деле, чтобы выразить его результат, математики прибегают к последовательности функций, известной как иерархия Аккермана. Первая функция в этой иерархии называется просто DOUBLE(x). Как подсказывает название (double — значит, удвоить), эта функция удваивает значение x. Так DOUBLE(1) равно 2, DOUBLE(50) равно 100. Вторая функция, EXPONENT(x), может быть описана как 2 в степени x, и, следовательно, EXPONENT(3) равно 8. Можно также выразить EXPONENT через DOUBLE. Например, чтобы найти EXPONENT(3), мы удваиваем 1, затем удваиваем результат предыдущего действия и затем снова удваиваем результат. На самом деле любая функция в иерархии Аккермана определяется через предыдущую.
Итак, третью функцию этой иерархии, TOWER(x), можно выразить с помощью функции EXPONENT. TOWER(3), например, — это 2 в степени 2 в степени 2, что равно 2 в степени 4, т.е. 16. TOWER(x) иногда записывают в виде «башни» (tower — значит, башня) показателей степеней,
| 2 ...2 | |
| 2 | 2 |
где x — число двоек в этой башне. Но даже функция TOWER(x) растёт недостаточно быстро, чтобы можно было записать результат Ван дер Вардена.
Следующую функцию, известную под шуточным прозвищем WOW(x) (английское междометие WOW примерно соответствует русским «Ой!», «Ах!» и «Ну и ну!». — Перев.), можно найти, если начать с 1 и применить x раз функцию TOWER. Тогда,
|
WOW(1) = TOWER(1) = 2, WOW(2) = TOWER(2) = 4, WOW(3) = TOWER(4) = 65536. |
Чтобы найти WOW(4), нужно вычислить TOWER(65536). Чтобы это сделать, нужно начать с 1 и применить функцию EXPONENT 65536 раз. Даже применение функции EXPONENT всего лишь пять раз даёт 265536 , — число, которое, будучи записанным цифра за цифрой, заполнило бы две страницы этого журнала. На самом деле даже число, заполняющее все страницы всех книг и всю память всех компьютеров, всё же останется несравнимым с WOW(4).
Тем не менее, чтобы всё-таки записать результат Ван дер Вардена, придётся определить функцию, которая растёт ещё быстрее. Функция ACKERMANN(x) определяется последовательностью DOUBLE(1), EXPONENT(2), TOWER(3), WOW(4) итакдалее. ACKERMANN(x) в конце концов растёт быстрее любой функции в этой иерархии. Доказательство Ван дер Вардена даёт следующий количественный результат: если числа 1, 2, ..., ACKERMANN(k) раскрашены двумя красками, то всегда существует одноцветная арифметическая прогрессия длиной k.