Проблема булевых пифагоровых троек - это проблема теории Рамсея о том, могут ли положительные целые числа быть окрашенными в красный и синий цвет, чтобы никакие пифагоровы тройки не состояли из всех красных или всех синих элементов. Проблема булевых пифагоровых троек была решена Марином Хеуле , Оливером Куллманном и Виктором В. Мареком в мае 2016 года с помощью компьютерного доказательства . [1]
Заявление
Задача спрашивает, можно ли раскрасить каждое из положительных целых чисел в красный или синий цвет, чтобы не было пифагоровой тройки целых чисел a , b , c , удовлетворяющих все одного цвета.
Например, в тройке Пифагора 3, 4 и 5 (), если 3 и 4 окрашены в красный цвет, то 5 должен быть окрашен в синий цвет.
Решение
Marijn Heule , Оливер Куллманн и Виктор В. Марек показали, что такая раскраска возможна только до числа 7824. Фактическая формулировка доказанной теоремы такова.
Теорема - множество {1,. . . , 7824} можно разбить на две части, так что ни одна часть не содержит пифагорова тройку, а это невозможно для {1,. . . , 7825}. [2]
Для чисел до 7825 существует 2 7825 ≈ 3,63 × 10 2355 возможных раскрасок . Эти возможные раскраски были логически и алгоритмически сужены до примерно триллиона (все еще очень сложных) случаев, и они были исследованы с помощью решателя логической выполнимости . Создание доказательства заняло около 4 процессорных лет вычислений в течение двух дней на суперкомпьютере Stampede в Техасском центре передовых вычислений и сгенерировало предположительное доказательство объемом 200 терабайт, которое было сжато до 68 гигабайт.
Статья с описанием доказательства была опубликована на конференции SAT 2016 [2], где она получила награду за лучшую работу. [3] На рисунке ниже показано возможное семейство раскрасок для набора {1, ..., 7824} без одноцветной пифагоровой тройки, а белые квадраты могут быть окрашены в красный или синий цвет, при этом удовлетворяя этому условию.
Приз
В 1980-х Рональд Грэм предложил премию в 100 долларов за решение проблемы, которая теперь была присуждена Марин Хойле . [1]
Обобщения
По состоянию на 2018 год проблема все еще открыта для более чем двух цветов, то есть, если существует k- раскраска ( k ≥ 3) положительных целых чисел, такая, что никакие пифагоровы тройки не имеют того же цвета. [4]
Смотрите также
Рекомендации
- ^ a b Лэмб, Эвелин (26 мая 2016 г.). «Математическое доказательство в двести терабайт - самое большое доказательство за всю историю» . Природа . 534 : 17–18. Bibcode : 2016Natur.534 ... 17L . DOI : 10.1038 / nature.2016.19990 . PMID 27251254 .
- ^ а б Heule, Marijn JH; Куллманн, Оливер; Марек, Виктор В. (2016). «Решение и проверка булевых пифагоровых троек с помощью Cube-and-Conquer». In Creignou, Надя; Ле Берр, Даниэль (ред.). Теория и приложения тестирования выполнимости - SAT 2016: 19-я Международная конференция, Бордо, Франция, 5-8 июля 2016 г., Материалы . Конспект лекций по информатике. 9710 . С. 228–245. arXiv : 1605.00723 . DOI : 10.1007 / 978-3-319-40970-2_15 .
- ^ СБ 2016
- ^ Элиаху, Шалом; Фроментин, Жан; Марион-Поти, Вирджиния; Робиллиард, Денис (2018-10-02). «Неизбежны ли монохроматические пифагорейские тройки при морфических раскрасках?» . Экспериментальная математика . 27 (4): 419–425. arXiv : 1605.00859 . DOI : 10.1080 / 10586458.2017.1306465 . ISSN 1058-6458 .