В задаче по «упаковке цветов графа» (в оригинале packing coloring, — прим. пер.) спрашивается, сколько чисел необходимо для заполнения бесконечной сетки так, чтобы идентичные числа никогда не оказывались слишком близко друг к другу. И новый арифметический эксперимент с использованием компьютера даёт на удивление простой ответ.
Сколько чисел потребуется для заполнения бесконечной сетки так, чтобы расстояние между вхождениями одного числа было больше самого этого числа?
Прим. пер.: есть некая неуверенность в корректности термина «упаковка», хотя в теории графов он вполне используется. Буду признателен, если сведущие читатели подскажут, как выразиться правильнее.
Будучи студентом последнего курса Университета Чили, Бернардо Суберкасо смотрел на применение компьютеров для выполнения математических расчётов свысока. По его мнению, это противоречило реальным интеллектуальным изысканиям.
Бернардо говорил так: «Присутствует некое инстинктивное отторжение использования компьютеров для решения задач, будто это идёт вразрез с идеальной красотой или элегантностью фантастического доказательства».
Но затем в 2020 году он влюбился и, как это часто бывает, его приоритеты изменились. Объектом его одержимости стал вопрос, который он увидел на онлайн-форуме. Большинство задач он просматривал и забывал, но эта зацепила его крепко.
«Первым делом я лайкнул этот пост в группе на Facebook в надежде позднее получить уведомление, когда будет опубликовано решение», — сказал он.
Задача требовала заполнить бесконечную сетку числами и, как оказалось, не относилась к разряду развлекательных. Для её решения Суберкасо пришлось покинуть Чили и поступить в аспирантуру Университета Карнеги-Меллона (Carnegie-Mellon University, CMU).
Тогда, в августе 2021 года, он по счастливой случайности познакомился с Марейн Хёлем, учёным в области информатики, который использовал обширные компьютерные возможности для разрешения сложных математических вопросов. Суберкасо спросил Хёля, не желает ли тот попробовать решить и его задачу, в результате чего между ними возникло сотрудничество, кульминацией которого в январе того же года стало решение, которое можно обобщить одним числом: 15.
▍ Все возможные способы
В 2002 году Уэйн Годдард из Университета Клемсона и его коллеги-математики разбирали задачи комбинаторики, пытаясь найти новые идеи в области фундаментальных вопросов о раскрашивании карт в условиях определённых ограничений.
В конечном итоге они пришли к задаче, начинающейся с сетки, подобной клетчатой бумаге, продолжающейся бесконечно. Целью было заполнить эту сетку числами при всего одном ограничении: расстояние между всеми вхождениями одного и того же числа должно быть больше самого этого числа. Измерялось это расстояние путём сложения вертикального и горизонтального разделения позиций чисел, то есть с помощью «метрики Манхэттена». Пара единиц не может занять соседние клетки, разделённые манхэттенским расстоянием 1, но их можно разместить в клетках, соседствующих по диагонали, манхэттенское расстояние между которыми равно 2.
Друг Бернарда Суберкасо разработал игру, напоминающую «Минёра», которая позволила ему быстро тестировать возможные решения. Эдвард Чен
Изначально Годдард с коллегами хотели узнать, окажется ли возможным заполнить бесконечную сетку конечным набором чисел. Но к моменту публикации ими этой задачи «упаковки цветов графа» в журнале Ars Combinatorica в 2008 году они уже доказали, что её можно решить с использованием 22 чисел. Они также знали, что её нельзя решить с помощью всего пяти чисел. Это означало, что фактический ответ – минимальное количество необходимых чисел – лежал где-то между.
В действительности исследователи не заполняли бесконечную сетку. Им этого не потребовалось. Было достаточно взять небольшую её часть – к примеру, квадрат 10х10 – заполнить его числами и затем продемонстрировать, какие копии этого заполненного подмножества можно поместить рядом друг с другом, подобно выкладыванию напольной плитки.
Когда Суберкасо впервые узнал об этой задаче, он начал перебирать различные варианты плиток, используя ручку и бумагу. Он рисовал сетки чисел, перечёркивал, пробовал снова… Вскоре такой подход его вымотал, и он попросил друга разработать онлайн-инструмент, который бы напоминал игру «Минёр» и позволял ему быстро тестировать разные комбинации. После ещё нескольких недель работы он убедился, что нет способа упаковать сетку с использованием восьми чисел, но дальше продвинуться ему не удавалось – было слишком много потенциальных фигур, которые могли образовывать плитки, и слишком много способов, которыми их можно было заполнить числами.
Проблема, как это прояснилось позднее, заключалась в том, что гораздо труднее продемонстрировать невозможность заполнения сетки определённым набором чисел, чем возможность этого.
«Это показывает не просто то, что какой-то способ не работает, а то, что не работает любой возможный способ», — сказал Годдард.
После того, как Суберкасо начал учёбу в CMU и убедил Хёля вести совместную работу, они быстро нашли способ заполнить сетку с помощью 15 чисел. Они также смогли исключить возможность решения задачи с использованием всего 12 чисел. Но их ощущение триумфа длилось недолго, поскольку они обнаружили, что просто воссоздают давно полученные результаты. Ещё в 2017 году исследователи уже узнали, что ответ будет не меньше 13 и не больше 15.
Марейн Хёль специализируется на использовании компьютерного потенциала для решения сложных математических вопросов. Университет Карнеги-Меллона
Для первокурсника, который уговорил своего профессора работать с ним над его хобби-задачей, это открытие оказалось шокирующим. Суберкасо, обобщая в своём посте проделанный ими труд, выразился так: «Я был в ужасе. По сути, я в течение нескольких месяцев работал над задачей, не осознавая этого, и даже хуже – из-за меня Марейн потратил на неё своё время!»
Тем не менее, сам Хёль нашёл открытие уже известных ранее результатов вдохновляющим. Это указывало на то, что другие исследователи сочли задачу достаточно важной, чтобы над ней трудиться, и подтвердило для него, что единственным достойным получения результатом было полное её решение.
«Когда мы выяснили, что над этой задачей трудятся уже 20 лет, это полностью изменило картину», — сказал он.
▍ «Недостойный» подход
В течение долгих лет Хёль строил карьеру за счёт того, что находил эффективные способы поиска среди огромного числа возможных комбинаций. Его подход назывался решением SAT – сокращённо от «satisfiability» (выполнимость условий, — прим. пер.). Он состоит в построении длинной формулы, называемой булевой, которая может иметь два возможных результата: 0 или 1. Если результат 1, значит формула верна и требования задачи удовлетворены.
Для рассматриваемой задачи по заполнению сетки переменная в этой формуле может представлять то, занята ли определённая клетка числом. Компьютер ищет способы присвоить переменные так, чтобы формула оказалась верна. Если компьютеру это удаётся, то вы узнаёте, что можно заполнить сетку при установленных вами условиях.
К сожалению, простое кодирование этой задачи в виде булевой формулы может растянуться на многие миллионы членов – компьютер, или даже их сеть, могут работать бесконечно, тестируя все возможные способы присваивания переменных.
«Попытка проделать это методом перебора при наивном подходе затянулась бы до конца существования вселенной, — говорил Годдард. – Поэтому необходимы эффективные упрощения, чтобы свести эту затею хотя бы в рамки возможного».
Более того, при каждом добавлении в алгоритм нового числа ввиду увеличения возможных вариантов вычислений задача усложняется примерно в 100 раз. То есть, если сеть работающих параллельно компьютеров сможет исключить в качестве ответа 12 за день вычислений, то для исключения 13 им потребуется 100 дней.
Хёль и Суберкасо признали масштабирование вычислительного подхода методом перебора в некотором смысле «недостойным». «У нас имелось несколько перспективных идей, поэтому мы были настроены „оптимизировать свой подход, пока не сможем решить задачу в пределах 48 часов вычислений кластером компьютеров“», — говорил Суберкасо.
Для этого им нужно было придумать способ ограничить число комбинаций, которые должен перебрать вычислительный кластер.
«Они хотят не просто её решить, но решить её впечатляющим образом», — заявил на это Александ Сойфер из Университета Колорадо.
Хёль и Суберкасо понимали, что многие комбинации, по сути, одинаковы. Если вы пытаетесь заполнить плитку в форме бриллианта восемью разными числами, то не важно, поместите ли вы первое из них на одну клетку выше и правее центра или же на одну клетку ниже и левее от него. Эти две позиции окажутся симметричны относительно друг друга и ограничат очередное действие одинаково, поэтому проверять их обе смысла нет.
Если бы каждую задачу упаковки можно было решить с помощью рисунка шахматной доски, где диагональная сетка из единиц охватывает всё пространство (например, чёрные клетки на доске), то вычисления бы сильно упростились. Да, это не всегда так, как в данном примере конечной плитки, упакованной 14 числами. Шахматный рисунок необходимо нарушить в некоторых местах ближе к верхнему левому углу. – Бернардо Суберкасо и Марейн Хёль.
Хёль и Суберкасо добавили правила, которые позволили компьютеру рассматривать симметричные комбинации как равнозначные, что снизило общее время поиска в восемь раз. Они также задействовали технику под названием «cube and conquer» (утраивай и властвуй), которую Хёль разработал в рамках своего прошлого проекта. Эта техника позволила им тестировать больше комбинаций параллельно. Если вы знаете, что заданная клетка содержит 3, 5 или 7, то можете разделить задачу и протестировать каждую из этих трёх возможностей одновременно на разных кластерах компьютеров.
К январю 2022 года эти доработки позволили исследователям исключить в качестве ответа 13, на что ушло два дня вычислительного времени. Так у них осталось два возможных ответа: 14 или 15.
▍ Большой плюс
Чтобы исключить 14 и решить таким образом задачу, Хёлю и Суберкасо пришлось искать дополнительные способы ускорить компьютерный поиск.
Изначально они написали булеву формулу, которая присваивала переменные каждой отдельной клетке сетки. Но в сентябре 2022 года им стало ясно, что не обязательно продолжать вычисления, перебирая клетки поочерёдно. Они выяснили, что будет гораздо эффективнее рассматривать небольшие области, состоящие из пяти клеток в форме символа +.
Тогда исследователи переписали свою формулу так, чтобы несколько переменных представляли вопросы вроде: «Есть ли где-то в этой +-образной области число 7?» Компьютеру не нужно было определять, где конкретно в этой области может находиться 7. Ему было достаточно выяснить, есть ли это число там вообще, для чего требовалось значительно меньше вычислительных затрат.
«Использование переменных, которые отражают только плюсы, а не конкретные расположения чисел, оказалось намного эффективнее, чем рассматривание этих чисел в конкретных клетках», — сказал Хёль.
За счёт нового подхода с использованием техники анализа «плюсов» исследователи в ходе проведённого в ноябре 2022 года эксперимента исключили в качестве ответа 14, затратив на это меньше времени, чем на исключение 13. В течение следующих четырёх месяцев они дополнительно проверяли корректность полученных результатов – это почти столько же времени, сколько они затратили на то, чтобы помочь компьютеру прийти к такому заключению изначально.
«Очень воодушевляла мысль о том, что какой-то, казалось бы, побочный вопрос, поставленный нами в каком-то случайном журнале, заставил целые группы людей потратить, как в итоге выяснилось, месяцы своего времени на поиск его решения». — заявил Годдард.
Для Суберкасо это был первый реальный триумф в его исследовательской карьере. И хотя это мог быть не тот вид «идеального» открытия, который юный учёный поначалу себе представлял, работая в сфере математики, в итоге оно всё же принесло ему отдельное интеллектуальное вознаграждение.
«Это непонимание структуры, когда вы даёте мне доску, и я могу показать вам, почему ответ 15, — говорил он. – Но мы смогли разобраться, как работают ограничения задачи, насколько лучше использовать 6 здесь или 7 там. Мы выработали глубокое интуитивное понимание».
Пол-лимона подарков от RUVDS. Отвечай на вопросы и получай призы 🍋
Автор: Дмитрий Брайт
