Введение

Фундаментальный комбинаторный результат теории Рамзи

В математике теорема Хейлса — Джеветта является фундаментальным комбинаторным результатом теории Рамзи, названным в честь Альфреда В. Хейлса и Роберта И. Джеветта, и касающимся степени, в которой объекты высокой размерности неизбежно должны проявлять некоторую комбинаторную структуру; для таких объектов невозможно быть «полностью случайными». Неформальное геометрическое утверждение теоремы заключается в том, что для любых положительных целых чисел n и c существует число H, такое, что если ячейки n-мерного куба размером H × H × … × H (n раз) окрашены в c цветов, то должна существовать строка, столбец или определённая диагональ (подробности ниже) длиной n, все ячейки которой окрашены в один и тот же цвет. Иными словами, при фиксированных n и c, многомерное, многопользовательское обобщение игры «крестики-нолики» с c игроками, где нужно выстроить n в ряд, не может закончиться вничью, независимо от величины n, количества игроков c и последовательности ходов, при условии, что игра ведётся на доске достаточно высокой размерности H. Используя стандартный аргумент о перехвате стратегии, можно заключить, что если два игрока ходят по очереди, то первый игрок имеет выигрышную стратегию при достаточно большом H, хотя практический алгоритм для её получения неизвестен.

Доказательство теоремы Хейлса и Джеветта (в особом случае)

Теперь мы доказываем теорему Хейлса — Джеветта в специальном случае n = 3, c = 2, H = 8, обсуждаемом выше. Идея состоит в том, чтобы свести эту задачу к доказательству более простых версий теоремы Хейлса — Джеветта (в этом конкретном случае — к случаям n = 2, c = 2, H = 2 и n = 2, c = 6, H = 6). Общий случай теоремы Хейлса — Джеветта можно доказать аналогичными методами, используя математическую индукцию. Каждый элемент гиперкуба W — это строка из восьми чисел от 1 до 3, например, 13211321 является элементом гиперкуба. Мы предполагаем, что этот гиперкуб полностью заполнен «нулями» и «крестами». Мы будем использовать доказательство от противного и предположим, что ни множество нулей, ни множество крестов не содержат комбинаторной линии. Если мы зафиксируем первые шесть элементов такой строки и позволим последним двум изменяться, мы получим обычную доску для крестиков-ноликов, например, «132113??» дает такую доску. Для каждой такой доски «abcdef??» мы рассматриваем позиции «abcdef11», «abcdef12», «abcdef22». Каждая из них должна быть заполнена нулем или крестом, поэтому по принципу Дирихле два из них должны быть заполнены одним и тем же символом. Поскольку любые два из этих положений являются частью комбинаторной линии, третий элемент этой линии должен быть занят противоположным символом (поскольку мы предполагаем, что ни одна комбинаторная линия не имеет всех трех элементов, заполненных одним и тем же символом). Другими словами, для каждого выбора «abcdef» (который можно рассматривать как элемент шестимерного гиперкуба W) существует шесть (пересекающихся) возможностей: abcdef11 и abcdef12 — нули; abcdef13 — крест. abcdef11 и abcdef22 — нули; abcdef33 — крест. abcdef12 и abcdef22 — нули; abcdef32 — крест. abcdef11 и abcdef12 — кресты; abcdef13 — ноль. abcdef11 и abcdef22 — кресты; abcdef33 — ноль. abcdef12 и abcdef22 — кресты; abcdef32 — ноль. Таким образом, мы можем разделить шестимерный гиперкуб W на шесть классов, соответствующих каждой из вышеуказанных шести возможностей. (Если элемент abcdef удовлетворяет нескольким возможностям, мы можем выбрать одну из них произвольно, например, выбрав самую высокую в вышеуказанном списке). Теперь рассмотрим семь элементов 111111, 111112, 111122, 111222, 112222, 122222, 222222 в W. По принципу Дирихле два из этих элементов должны попасть в один класс. Предположим, например, что 111112 и 112222 относятся к классу (5), таким образом, 11111211, 11111222, 11222211, 11222222 — кресты, а 11111233, 11222233 — нули. Но теперь рассмотрим позицию 11333233, которая должна быть заполнена либо крестом, либо нулем. Если она заполнена крестом, то комбинаторная линия 11xxx2xx полностью заполнена крестами, что противоречит нашей гипотезе. Если вместо этого она заполнена нулем, то комбинаторная линия 11xxx233 полностью заполнена нулями, что опять же противоречит нашей гипотезе. Аналогично, если любые два других из вышеуказанных семи элементов W попадают в один и тот же класс. Поскольку во всех случаях имеется противоречие, исходная гипотеза должна быть ложной; таким образом, должна существовать по крайней мере одна комбинаторная линия, состоящая полностью из нулей или полностью из крестов. Вышеуказанный аргумент был несколько избыточен; на самом деле та же теорема справедлива для H = 4. Если расширить вышеуказанный аргумент на общие значения n и c, то H будет расти очень быстро; даже когда c = 2 (что соответствует игре в крестики-нолики с двумя игроками), H, полученный вышеуказанным аргументом, растет так же быстро, как функция Аккермана. Первая примитивно рекурсивная оценка была получена Сахароном Шелахом и до сих пор является наилучшей известной оценкой для числа Хейлса — Джеветта H = H(n, c).