В математике , то Hales-Джьюетты теорема является фундаментальным комбинаторным результатом теории Рамсея имени Альфреда В. Хейлза и Роберт И. Jewett, относительно той степени , в которой многомерные объекты обязательно должны проявлять некоторую комбинаторную структуру; такие объекты не могут быть «полностью случайными». [1]
Неформальная геометрическая формулировка теоремы состоит в том, что для любых натуральных чисел n и c существует такое число H , что если клетки H -мерного куба n × n × n × ... × n раскрашены в c цветов, существует должен быть одной строкой, столбцом или определенной диагональю (подробнее см. ниже) длины n, все ячейки которой одного цвета. Другими словами, многомерное, многопользовательское, n -в-рядное обобщение игры в крестики-нолики не может закончиться ничьей, независимо от того, насколько велико n , независимо от того, сколько людейс играют, и независимо от того , какой игрок играет каждый ход, если только она играет на борту достаточно высокой размерности H . Используя стандартный аргумент кражи стратегии , можно, таким образом, заключить, что если два игрока чередуются, то первый игрок имеет выигрышную стратегию, когда H достаточно велико, хотя практический алгоритм для получения этой стратегии неизвестен.
Более формально пусть WH
n- множество слов длины H над алфавитом из n букв; то есть, набор последовательностей {1, 2, ..., п } длины Н . Этот набор образует гиперкуб, о котором идет речь в теореме. Переменная слово ш ( х ) над WH
nпо-прежнему имеет длину H, но включает специальный элемент x вместо хотя бы одной из букв. Слова w (1), w (2), ..., w ( n ), полученные заменой всех экземпляров специального элемента x на 1, 2, ..., n , образуют комбинаторную линию в пространстве WH
n; комбинаторные линии соответствуют строкам, столбцам и (некоторым) диагоналям гиперкуба . Затем теорема Хейлза-Джеветта утверждает, что для данных натуральных чисел n и c существует натуральное число H , зависящее от n и c , такое, что для любого разбиения WH
nна c частей, есть хотя бы одна часть, содержащая целую комбинаторную строку.
Например, возьмем n = 3, H = 2 и c = 2. Гиперкуб WH
nв данном случае это просто стандартная доска для крестиков-ноликов с девятью позициями:
11 | 12 | 13 |
21 год | 22 | 23 |
31 год | 32 | 33 |
Типичной комбинаторной строкой будет слово 2x, которое соответствует строке 21, 22, 23; другая комбинаторная линия - это xx, которая является строкой 11, 22, 33. (Обратите внимание, что строки 13, 22, 31, будучи допустимой строкой для игры в крестики-нолики , не считаются комбинаторной линией.) В частном случае теорема Хейлса – Джеветта неприменима; можно разделить доску для крестиков-ноликов на два набора, например {11, 22, 23, 31} и {12, 13, 21, 32, 33}, ни один из которых не содержит комбинаторной линии (и будет соответствовать к ничьей в игре в крестики-нолики ). С другой стороны, если мы увеличим H , скажем, до 8 (так, чтобы доска стала восьмерной , с 3 8 = 6561 позициями), и разделим эту доску на два набора («нули» и «крестики») , то один из двух наборов должен содержать комбинаторную линию (т.е. в этом варианте крестиков-ноликов ничья невозможна ). Доказательство см. Ниже.
Доказательство теоремы Хейлза – Джеветта (в частном случае).
Теперь докажем теорему Хейлза – Джеветта в частном случае n = 3, c = 2, H = 8, обсужденном выше. Идея состоит в том, чтобы свести эту задачу к доказательству более простых версий теоремы Хейлза – Джеветта (в данном конкретном случае к случаям n = 2, c = 2, H = 2 и n = 2, c = 6, H = 6). Можно доказать общий случай теоремы Хейлза – Джеветта аналогичными методами, используя математическую индукцию .
Каждый элемент гиперкуба W8
3представляет собой строку из восьми чисел от 1 до 3, например, 13211321 - элемент гиперкуба . Мы предполагаем, что этот гиперкуб полностью заполнен «нулями» и «крестиками». Мы воспользуемся доказательством от противного и предположим, что ни набор нулей, ни набор крестов не содержат комбинаторной прямой. Если мы зафиксируем первые шесть элементов такой строки и позволим последним двум изменяться, мы получим обычную доску для крестиков-ноликов , например 132113 ?? дает такую доску. Для каждой такой платы abcdef ?? мы рассматриваем позиции abcdef11, abcdef12, abcdef22. Каждый из них должен быть заполнен нулем или крестом, поэтому по принципу ячейки два из них должны быть заполнены одним и тем же символом. Поскольку любые две из этих позиций являются частью комбинаторной строки, третий элемент этой строки должен быть занят противоположным символом (поскольку мы предполагаем, что ни одна комбинаторная строка не содержит всех трех элементов, заполненных одним и тем же символом). Другими словами, для каждого выбора abcdef (который можно рассматривать как элемент шестимерного гиперкуба W6
3) существует шесть (перекрывающихся) возможностей:
- abcdef11 и abcdef12 - нули; abcdef13 - это крест.
- abcdef11 и abcdef22 - нули; abcdef33 - это крест.
- abcdef12 и abcdef22 - нули; abcdef32 - это крест.
- abcdef11 и abcdef12 - крестики; abcdef13 - это ноль.
- abcdef11 и abcdef22 - крестики; abcdef33 - это ноль.
- abcdef12 и abcdef22 - крестики; abcdef32 - это ноль.
Таким образом, мы можем разбить шестимерный гиперкуб W6
3на шесть классов, соответствующих каждой из шести вышеперечисленных возможностей. (Если элемент abcdef подчиняется нескольким возможностям, мы можем выбрать один произвольно, например, выбрав самый высокий в приведенном выше списке).
Теперь рассмотрим семь элементов 111111, 111112, 111122, 111222, 112222, 122222, 222222 в W6
3. По принципу «ящика» два из этих элементов должны относиться к одному классу. Предположим, например, что 111112 и 112222 попадают в класс (5), таким образом, 11111211, 11111222, 11222211, 11222222 - крестики, а 11111233, 11222233 - нули. Но теперь рассмотрим позицию 11333233, которую нужно заполнить либо крестиком, либо нулем. Если она заполнена крестиком, то комбинаторная линия 11xxx2xx полностью заполнена крестиками, что противоречит нашей гипотезе. Если вместо этого она заполнена нулем, то комбинаторная строка 11xxx233 полностью заполнена нулями, что снова противоречит нашей гипотезе. Аналогично, если любые другие два из семи указанных выше элементов W6
3попадают в один класс. Поскольку во всех случаях мы имеем противоречие, исходная гипотеза должна быть ложной; таким образом, должна существовать по крайней мере одна комбинаторная линия, состоящая полностью из нулей или полностью из крестов.
Приведенный выше аргумент был несколько расточительным; фактически та же теорема верна для H = 4. [2] Если распространить приведенные выше рассуждения на общие значения n и c , то H будет расти очень быстро; даже когда c = 2 (что соответствует крестикам-ноликам с двумя игроками ), H, заданный вышеупомянутым аргументом, растет так же быстро, как функция Аккермана . Первые примитивно рекурсивный связанный связано с Сахарон Шелов , [3] и до сих пор наиболее известными связаны в целом для числа Хейлза-Джеветт H = H ( п , с ).
Связь с другими теоремами
Обратите внимание, что приведенный выше аргумент также дает следующее следствие: если мы допустим, что A будет набором всех восьмизначных чисел, все цифры которых равны 1, 2, 3 (таким образом, A содержит числа, такие как 11333233), и мы раскрасим A двумя colors, то A содержит хотя бы одну арифметическую прогрессию длины три, все элементы которой одного цвета. Это просто потому, что все комбинаторные линии, появляющиеся в приведенном выше доказательстве теоремы Хейлза – Джеветта, также образуют арифметические прогрессии в десятичной системе счисления . Более общая формулировка этого аргумента может быть использована, чтобы показать, что теорема Хейлза – Джеветта обобщает теорему Ван дер Вардена . Действительно, теорема Хейлза – Джеветта существенно более сильная.
Так же, как теорема ван дер Вардена имеет более сильную версию плотности в теореме Семереди, теорема Хейлса – Джеветта также имеет версию плотности. В этой усиленной версии теоремы Хейлза – Джеветта вместо раскраски всего гиперкуба WH
nв c цветов, задано произвольное подмножество A гиперкуба WH
nс некоторой заданной плотностью 0 <δ <1. Теорема утверждает, что если H достаточно велико в зависимости от n и δ, то множество A обязательно должно содержать целую комбинаторную линию.
Теорема плотности Хейлза – Джеветта была первоначально доказана Фюрстенбергом и Кацнельсоном с использованием эргодической теории . [4] В 2009 году проект Polymath разработал новое доказательство [5] [6] теоремы Хейлса – Джеветта о плотности, основанное на идеях доказательства теоремы об углах . [7] Додос, Канеллопулос и Тирос дали упрощенную версию доказательства Polymath. [8]
Теорема Хейлза – Джеветта обобщается теоремой Грэма – Ротшильда для многомерных комбинаторных кубов .
Смотрите также
Рекомендации
- ^ Хейлз, Альфред В .; Джеветт, Роберт И. (1963). «Регулярность и позиционные игры» . Пер. Амер. Математика. Soc. 106 (2): 222–229. DOI : 10.1090 / S0002-9947-1963-0143712-1 . Руководство по ремонту 0143712 .
- ^ Хиндман, Нил; Тресслер, Эрик (2014). «Первое нетривиальное число Хейлза-Джеветта - четыре» (PDF) . Ars Combinatoria . 113 : 385–390. Руководство по ремонту 3186481 .
- ^ Шелах, Сахарон (1988). «Примитивные рекурсивные оценки для чисел Ван дер Вардена» . J. Amer. Математика. Soc. 1 (3): 683–697. DOI : 10.2307 / 1990952 . JSTOR 1990952 . Руководство по ремонту 0929498 .
- ^ Фюрстенберг, Гиллель ; Кацнельсон, Ицхак (1991). "Версия плотности теоремы Хейлса-Джеветта". Журнал d'Analyse Mathématique . 57 (1): 64–119. DOI : 10.1007 / BF03041066 . Руководство по ремонту 1191743 .
- ^ DHJ Polymath (2012). «Новое доказательство плотности теоремы Хейлса – Джеветта» . Анналы математики . 175 (3): 1283–1327. DOI : 10.4007 / annals.2012.175.3.6 . Руководство по ремонту 2912706 .
- ^ Гауэрс, Уильям Тимоти (2010). «Polymath и теорема Хейлса-Джеветта о плотности». В Барани, Имре; Solymosi, József (ред.). Необычный ум . Математические исследования общества Бойяи. 21 . Будапешт: Математическое общество Яноша Бойяи. С. 659–687. DOI : 10.1007 / 978-3-642-14444-8_21 . ISBN 978-963-9453-14-2. Руководство по ремонту 2815619 .
- ^ Айтай, Миклош; Семереди, Эндре (1974). «Наборы точек решетки, не образующие квадратов». Stud. Sci. Математика. Hungar . 9 : 9–11. Руководство по ремонту 0369299 .
- ^ Додос, Панделис; Канеллопулос, Василис; Тирос, Константинос (2014). «Простое доказательство плотности теоремы Хейлса-Джеветта». Int. Математика. Res. Нет. IMRN . 2014 (12): 3340–3352. arXiv : 1209,4986 . DOI : 10.1093 / imrn / rnt041 . Руководство по ремонту 3217664 .
Внешние ссылки
- Полное доказательство HJT - начинается на слайде 57.
- Статья в журнале Science News о совместном доказательстве теоремы Хейлза-Джеветта о плотности
- Сообщение в блоге Стивена Ландсбурга, в котором обсуждается, как доказательство этой теоремы было совместно улучшено в блоге.