[Перевод] Джун Ха: ход конём из поэта в великие математики
В 2022 году Джун Ха (June Huh) был награжден медалью Филдса за революционный вклад в области комбинаторики, особенно за мосты, которые он построил между комбинаторикой и алгебраической геометрией. Сложно поверить, что человек, получивший медаль за выдающиеся открытия в математике, раньше совершенно её не любил, и вообще мечтал стать поэтом. Возможно, мир никогда не узнал бы этого выдающегося математика, если бы не… шахматы. А именно, задачи на ход коня. Вот как всё было:
Джун Ха на Международном конгрессе математиков 2018 года в Рио-де-Жанейро
Поэзия математики
В юности Ха пробовал себя в разных сферах. Сначала бросил школу, чтобы стать поэтом. После неудачи на этом поприще хотел податься в научные журналисты, изучал физику и астрономию. Но что его совершенно не привлекало и не интересовало, так это математика. Пока однажды он не поиграл в хоррор 1995 года «The 11th Hour».
В игре нужно было расследовать серию ужасных событий, решая головоломки. Некоторые из них были особенно сложными. Ха долго бился над одной из них — над шахматной головоломкой:
На первый взгляд задачка кажется достаточно простой. У вас есть несколько клеток и всего четыре коня (кони ходят в форме буквы «Г», как в обычных шахматах). И нужно просто поменять местами черных и белых коней.
Вроде бы, и думать нечего: просто перемещаете коней, пока они не встанут, как надо. Но стоит начать это делать, как вы понимаете — всё не так просто. Молодому Ха потребовалась неделя, чтобы найти решение. Но для него это было не просто решением задачи, ему важно было разобраться, что это на самом деле означает.
В математическом смысле способ передвижения коней не имеет значения. Как не имеют значения форма и размер доски. Важна геометрия блоков и взаимосвязи между ними. По сути, шахматную головоломку можно интерпретировать как граф. Каждый конь может перейти на незанятое место на этом графе, и это существенно упрощает решение задачи.
Первым шагом устанавливаем обозначения:
Альтернативная визуализация задачи
Теперь, вместо того, чтобы представлять ходы коня геометрически, их можно представить как последовательность возможных ходов с одной клетки на другую.
Другой способ визуализации той же шахматной задачи. Конь из »1» может перепрыгнуть в »5», а затем в »7».
Конь может ходить с »1» на »5» и больше никуда. От »5» он может вернуться на »1» или на »7». Фактически, единственная клетка, с которой можно переместиться в три разных места, — это »2». В этом и заключается ключ к разгадке.
Когда мы добавляем коней, задача принимает такой вид:
На картинке выше становится гораздо понятнее, куда двигаться дальше. У нас есть клетка »9», которую мы можем использовать как буфер для одного коня, пока маневрируем тремя другими. Если мы хотим поменять местами белых и черных коней, нам просто нужно убирать черных по одному, а белых перемещать влево. Попробуйте!
Переводим на математические рельсы
Этот подход к визуализации задачи в математической форме очаровал Ха, и математика для него стала гораздо привлекательнее. Этот конкретный тип задач называется хроматическим многочленом.
Представьте, что у вас есть карта или сеть узлов, соединённых рёбрами, например, города, соединённые дорогами, или регионы на карте, очерченные границами.
Хроматический многочлен этой сети (или граф) говорит о количестве способов раскрасить узлы (или регионы) заданным количеством цветов так, чтобы никакие два соседних узла (или соседних региона) не имели один и тот же цвет.
Эта идея касается не только шахмат. Он имеет практическое применение в задачах логистики и оптимизации, статистической физике (особенно при изучении фазовых переходов) и сетевом анализе.
Перевод задач в математические выражения стал для Ха больше, чем просто хобби. На последнем году обучения в колледже Ха по‑настоящему влюбился в математику. Он посещал курсы Хейсуке Хиронаки, японского математика, получившего медаль Филдса в 1970 году. Ха стал его учеником и получил рекомендательное письмо. Это было странно и невероятно: студент, проваливший несколько курсов математики, вдруг получает восторженную рекомендацию от ведущего математика. Но письма оказалось недостаточно. Все университеты, в которые Ха подавал документы отказали ему. И только Университет Иллинойса в Урбане‑Шампейне поставил его в список ожидания и, в конце концов, принял.
Вот так, начиная путь с нелюбви к математике, Ха совершил революцию в области комбинаторики, вдохнув новую жизнь в эту область и переплетя её с некоторыми из самых эзотерических областей геометрии.
Однако Ха далеко не единственный математик, которого привлекают головоломки про шахматных коней.
Печально известная задача о ходе коня
Пожалуй, самая известная задача с конями — это так называемая «Задача о ходе коня» (Knight’s tour). Условия, опять же, очень просты. У вас есть квадратная шахматная доска заданного размера и один конь. Вам нужно переместить коня так, чтобы он побывал на каждой клетке, но не заходил на одну и ту же клетку дважды. Что‑то вроде этого:
Эту задачу можно применить к доскам разных размеров.
В широком смысле — это гамильтонова задача о путях в теории графов. Но в отличие от задачи Ха, эта возникла гораздо раньше.
Самое раннее известное упоминание «Задачи о ходе коня» относится к 9 веку и встречается в санскритском произведении. Кашмирский поэт и теоретик литературы Рудрата представил эту задачу как стихотворение из четырех строк по восемь слогов в каждой — ещё одно удивительное сочетание поэзии и математики.
Знаменитый математик Леонард Эйлер также рассматривал эту проблему, но именно Х.К. фон Варнсдорф разработал первый прослеживаемый алгоритм решения хода коня. Варнсдорф постулировал следующее правило: «Переместите коня на поле, с которого у него будет наименьшее количество последующих ходов».
Граф коня, показывающий все возможные пути коня на стандартной шахматной доске 8×8. Числа на каждом узле указывают количество возможных ходов, которые можно сделать из этой позиции.
Это простое правило оказалось удивительно эффективным, но оно не идеально. В подавляющем большинстве случаев оно позволяет решить задачу на досках размером менее 50×50, но не всегда.
Оказывается, найти работоспособный, обобщающий алгоритм для «Задачи о ходе коня» сложнее, чем может показаться. Это связано с явной сложностью больших досок. Например, наименьшая доска, для которой у задачи есть решение, — 5×5. Для доски такого размера существует более 1700 возможных обходов (обходы считаются разными, если они начинаются из разных мест или имеют разные траектории; их можно зеркально отображать или вращать).
Это число быстро возрастает.
n | Количество направленных обходов (открытых и закрытых) на доске n × n . |
1 | 1 |
2 | 0 |
3 | 0 |
4 | 0 |
5 | 1728 |
6 | 6 637 920 |
7 | 165 575 218 320 |
8 | 19 591 828 170 979 904 |
Примечательно, что эту задачу можно решить даже с помощью алгоритма нейронной сети. Впервые это обсуждалось в 1992 году в статье, написанной под руководством Ёсиясу Такефудзи из Университета Кейо в Японии. Сеть была настроена так, что каждый ход по сути являлся нейроном в сети.
Привлекательность подобных задачек о ходе коня, их удивительное богатство и глубина, сами по себе уже многое говорят о математике. Есть в ней одна черта, которую часто игнорируют: присущая ей красота закономерностей и решений.
Для Джун Ха это осознание пришло из творческих поисков и, казалось бы, несвязанной напрямую с математикой игровой головоломки. Но она показала, что пути к математическому успеху столь же разнообразны, как и люди, которые идут по ним.
Спасибо за внимание!
