Джун Ха: ход конём из поэта в великие математики

В 2022 году Джун Ха (June Huh) был награжден медалью Филдса за революционный вклад в области комбинаторики, особенно за мосты, которые он построил между комбинаторикой и алгебраической геометрией. Сложно поверить, что человек, получивший медаль за выдающиеся открытия в математике, раньше совершенно её не любил, и вообще мечтал стать поэтом. Возможно, мир никогда не узнал бы этого выдающегося математика, если бы не… шахматы. А именно, задачи на ход коня. Вот как всё было:

Поэзия математики

В юности Ха пробовал себя в разных сферах. Сначала бросил школу, чтобы стать поэтом. После неудачи на этом поприще хотел податься в научные журналисты, изучал физику и астрономию. Но что его совершенно не привлекало и не интересовало, так это математика. Пока однажды он не поиграл в хоррор 1995 года «The 11th Hour».

В игре нужно было расследовать серию ужасных событий, решая головоломки. Некоторые из них были особенно сложными. Ха долго бился над одной из них — над шахматной головоломкой:

На первый взгляд задачка кажется достаточно простой. У вас есть несколько клеток и всего четыре коня (кони ходят в форме буквы «Г», как в обычных шахматах). И нужно просто поменять местами черных и белых коней.

Вроде бы, и думать нечего: просто перемещаете коней, пока они не встанут, как надо. Но стоит начать это делать, как вы понимаете — всё не так просто. Молодому Ха потребовалась неделя, чтобы найти решение. Но для него это было не просто решением задачи, ему важно было разобраться, что это на самом деле означает.

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

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

Конь может ходить с «1» на «5» и больше никуда. От «5» он может вернуться на «1» или на «7». Фактически, единственная клетка, с которой можно переместиться в три разных места, — это «2». В этом и заключается ключ к разгадке.

Когда мы добавляем коней, задача принимает такой вид:

На картинке выше становится гораздо понятнее, куда двигаться дальше. У нас есть клетка «9», которую мы можем использовать как буфер для одного коня, пока маневрируем тремя другими. Если мы хотим поменять местами белых и черных коней, нам просто нужно убирать черных по одному, а белых перемещать влево. Попробуйте!

Переводим на математические рельсы

Этот подход к визуализации задачи в математической форме очаровал Ха, и математика для него стала гораздо привлекательнее. Этот конкретный тип задач называется хроматическим многочленом.

Представьте, что у вас есть карта или сеть узлов, соединённых рёбрами, например, города, соединённые дорогами, или регионы на карте, очерченные границами.

Хроматический многочлен этой сети (или граф) говорит о количестве способов раскрасить узлы (или регионы) заданным количеством цветов так, чтобы никакие два соседних узла (или соседних региона) не имели один и тот же цвет.

Эта идея касается не только шахмат. Он имеет практическое применение в задачах логистики и оптимизации, статистической физике (особенно при изучении фазовых переходов) и сетевом анализе.

Перевод задач в математические выражения стал для Ха больше, чем просто хобби. На последнем году обучения в колледже Ха по‑настоящему влюбился в математику. Он посещал курсы Хейсуке Хиронаки, японского математика, получившего медаль Филдса в 1970 году. Ха стал его учеником и получил рекомендательное письмо. Это было странно и невероятно: студент, проваливший несколько курсов математики, вдруг получает восторженную рекомендацию от ведущего математика. Но письма оказалось недостаточно. Все университеты, в которые Ха подавал документы отказали ему. И только Университет Иллинойса в Урбане‑Шампейне поставил его в список ожидания и, в конце концов, принял.

Вот так, начиная путь с нелюбви к математике, Ха совершил революцию в области комбинаторики, вдохнув новую жизнь в эту область и переплетя её с некоторыми из самых эзотерических областей геометрии.

Однако Ха далеко не единственный математик, которого привлекают головоломки про шахматных коней.

Печально известная задача о ходе коня

Пожалуй, самая известная задача с конями — это так называемая «Задача о ходе коня» (Knight’s tour). Условия, опять же, очень просты. У вас есть квадратная шахматная доска заданного размера и один конь. Вам нужно переместить коня так, чтобы он побывал на каждой клетке, но не заходил на одну и ту же клетку дважды. Что‑то вроде этого:

Эту задачу можно применить к доскам разных размеров.

В широком смысле — это гамильтонова задача о путях в теории графов. Но в отличие от задачи Ха, эта возникла гораздо раньше.

Самое раннее известное упоминание «Задачи о ходе коня» относится к 9 веку и встречается в санскритском произведении. Кашмирский поэт и теоретик литературы Рудрата представил эту задачу как стихотворение из четырех строк по восемь слогов в каждой — ещё одно удивительное сочетание поэзии и математики.

Знаменитый математик Леонард Эйлер также рассматривал эту проблему, но именно Х. К. фон Варнсдорф разработал первый прослеживаемый алгоритм решения хода коня. Варнсдорф постулировал следующее правило: «Переместите коня на поле, с которого у него будет наименьшее количество последующих ходов».

Это простое правило оказалось удивительно эффективным, но оно не идеально. В подавляющем большинстве случаев оно позволяет решить задачу на досках размером менее 50×50, но не всегда.

Оказывается, найти работоспособный, обобщающий алгоритм для «Задачи о ходе коня» сложнее, чем может показаться. Это связано с явной сложностью больших досок. Например, наименьшая доска, для которой у задачи есть решение, — 5×5. Для доски такого размера существует более 1700 возможных обходов (обходы считаются разными, если они начинаются из разных мест или имеют разные траектории; их можно зеркально отображать или вращать).

Это число быстро возрастает.

Примечательно, что эту задачу можно решить даже с помощью алгоритма нейронной сети. Впервые это обсуждалось в 1992 году в статье, написанной под руководством Ёсиясу Такефудзи из Университета Кейо в Японии. Сеть была настроена так, что каждый ход по сути являлся нейроном в сети.

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

Для Джун Ха это осознание пришло из творческих поисков и, казалось бы, несвязанной напрямую с математикой игровой головоломки. Но она показала, что пути к математическому успеху столь же разнообразны, как и люди, которые идут по ним.

Спасибо за внимание!