Булева проблема пифагоровых троек — одна из задач теории Рамсея .

Формулировка

Можно ли разделить множество натуральных чисел на две части таким образом, чтобы каждая часть не имела ни одной пифагоровой тройки ?

Замечание

В терминах покраски чисел проблема выглядит так: можно ли раскрасить натуральные числа в два цвета так, чтобы ни одна пифагорова тройка не была монохромной?

История

В 2015 году Джошуа Купер и Ральф Оверстрит раскрасили двумя цветами 7664 натуральных чисел так, что все пифагоровы тройки были разноцветными .

Марин Гейле, Оливер Кульман и Виктор Марек в мае 2016 года решили задачу. Они доказали, что множество натуральных чисел {1,…, 7824} можно поделить так, чтобы каждая часть не имела ни одной пифагоровой тройки, но это невозможно для {1,…, 7825} .

Теорема была доказана путём перебора всех вариантов с использованием 800 ядер суперкомпьютера Stampede в в течение двух дней. Размер файла с доказательством в формате DRAT достиг 200 терабайт . Из него был изготовлен и помещён в архив сертификат размером 68 гигабайт . Для 7824 натуральных чисел существует несколько решений проблемы, но для 7825 решений не найдено .

Статья Марин Гейле, Оливера Кульмана и Виктора Марека была выбрана для доклада на конференции SAT 2016, которая состоялась в Бордо ( Франция ) в июле 2016 года, и была признана лучшей работой .

См. также

• Теорема Рамсея
• Задача выполнимости булевых формул (SAT)
• Гипотеза Эрдёша — Секереша о выпуклых многоугольниках

Примечания