Проблема логических троек Пифагора - Boolean Pythagorean triples problem

В Проблема логических троек Пифагора это проблема от Теория Рамсея о том, есть ли положительные целые числа может быть окрашен в красный и синий цвет, чтобы не было Пифагорейские тройки состоят из всех красных или всех синих элементов. Проблема булевых пифагоровых троек была решена Марином Хеуле, Оливером Куллманном и Виктор В. Марек в мае 2016 г. компьютерное доказательство.[1]

утверждение

Задача спрашивает, можно ли окрасить каждое из положительных целых чисел в красный или синий цвет, чтобы никакая пифагорова тройка целых чисел а, б, c, удовлетворяющий все одного цвета.

Например, в тройке Пифагора 3, 4 и 5 (), если 3 и 4 окрашены в красный цвет, то 5 должен быть окрашен в синий цвет.

Решение

Марин Хеул, Оливер Куллманн и Виктор В. Марек показали, что такая раскраска возможна только до числа 7824. Фактическая формулировка доказанной теоремы такова.

Теорема —  Набор {1,. . . , 7824} можно разделить на две части, так что ни одна часть не содержит пифагорова тройку, а это невозможно для {1,. . . , 7825}.[2]

Есть 27825 ≈ 3.63×102355 возможные комбинации раскраски для чисел до 7825. Эти возможные раскраски были логически и алгоритмически сужены примерно до триллиона (все еще очень сложных) случаев, и они были исследованы с использованием Логическая выполнимость решатель. Создание доказательства заняло около 4-х процессорных лет вычислений в течение двух дней на суперкомпьютере Stampede в г. Техасский вычислительный центр и сгенерировал доказательство утверждения на 200 терабайт, которое было сжато до 68 гигабайт.

Статья с описанием доказательства была опубликована на конференции SAT 2016,[2] где он получил награду за лучшую бумагу.[3] На рисунке ниже показано возможное семейство раскрасок для набора {1, ..., 7,824} без одноцветной пифагоровой тройки, а белые квадраты могут быть окрашены в красный или синий цвет, при этом удовлетворяя этому условию.

Приз

В 80-е годы Рональд Грэм предложили приз в размере 100 долларов за решение проблемы, который теперь был присужден Марин Хеул.[1]

Обобщения

По состоянию на 2018 год проблема все еще открыта для более чем 2 цветов, то есть, если существует k-раскрашивание (k ≥ 3) натуральных чисел такие, что никакие пифагоровы тройки не имеют одинаковый цвет.[4]

Смотрите также

использованная литература

  1. ^ а б Лэмб, Эвелин (26 мая 2016 г.). «Математическое доказательство в двести терабайт - самое большое доказательство». Природа. 534: 17–18. Bibcode:2016Натура.534 ... 17л. Дои:10.1038 / природа.2016.19990. PMID  27251254.
  2. ^ а б Heule, Marijn J. H .; Куллманн, Оливер; Марек, Виктор В. (2016). «Решение и проверка булевых пифагоровых троек с помощью Cube-and-Conquer». In Creignou, Надя; Ле Берр, Даниэль (ред.). Теория и приложения тестирования выполнимости - SAT 2016: 19-я Международная конференция, Бордо, Франция, 5-8 июля 2016 г., Труды. Конспект лекций по информатике. 9710. С. 228–245. arXiv:1605.00723. Дои:10.1007/978-3-319-40970-2_15.
  3. ^ СБ 2016
  4. ^ Элиаху, Шалом; Фроментин, Жан; Марион-Поти, Вирджиния; Робиллиард, Денис (02.10.2018). "Неизбежны ли монохроматические пифагорейские тройки при морфических раскрасках?". Экспериментальная математика. 27 (4): 419–425. Дои:10.1080/10586458.2017.1306465. ISSN  1058-6458.