Математик из Гарвардского университета решил своего рода ферзевый гамбит 150-летней давности: восхитительную головоломку с n-ным количеством ферзей. В недавно опубликованном исследовании (это означает, что оно ещё не было рецензировано) Майкл Симкин, научный сотрудник Гарвардского центра математических наук и приложений, оценил решение сложной математической задачи, которая в общих чертах основана на правилах шахмат.
Ферзь считается самой сильной фигурой на доске, потому что он может двигаться в любом направлении, включая диагонали. Так сколько же ферзей может поместиться на шахматной доске так, чтобы они не попадались друг другу на пути?
Логика игры здесь похожа на головоломку судоку. Нужно расставить точки на доске так, чтобы они не пересекались.
Классическая шахматная доска представляет собой матрицу квадратов восемь на восемь. Самая известная версия головоломки соответствует доске, потому что в ней участвуют восемь ферзей — и в этом случае есть 92 решения. Но «проблема n ферзей» на этом не заканчивается; это потому, что её природа асимптотична, то есть ответы приближаются к неопределенной величине, достигающей бесконечности.
Фото: chessrussian.ru
До сих пор эксперты решали задачу для всех натуральных чисел до 27 ферзей на доске 27 на 27. Однако решения для двух или трёх нет, потому что нет возможного расположения ферзей, удовлетворяющего критериям. Но как насчет чисел выше 27? Для восьми ферзей существует всего 92 решения, а для 27 ферзей существует более 200 квадриллионов решений. Легко увидеть, как решение задачи для чисел выше 27 становится чрезвычайно громоздким или даже невозможным без большей вычислительной мощности, чем у есть на данный момент.
В своей работе Симкин подошёл к теме с помощью точной математической оценки количества решений при увеличении n. В конечном итоге он пришёл к следующей формуле: (0,143n)n. Другими словами, существует приблизительно (0,143n)n способов расставить ферзей так, чтобы ни один из них не атаковал друг друга на шахматной доске размером n на n.
Сама математика представляет собой сложный набор матричной алгебры, который занимает 50 страниц доказательств.
И интересно, что технически результаты Симкина всё ещё являются лишь оценкой! Но это лучше, чем то, с чем математики работали до сих пор. «На очень большой шахматной доске с миллионом ферзей, например, 0,143 умножается на один миллион, и получается около 143 000. Затем это число возводится в степень одного миллиона, то есть оно умножается само на себя столько раз. Окончательный ответ — цифра из пяти миллионов цифр», — поясняет Гарвард в пресс-релизе.
Фото: naukatehnika.com
Чтобы прийти к своему решению, Симкин сначала взял средние значения распределения ферзей по доске. Он использовал эти данные, чтобы установить значение нижней границы, то есть минимальное количество решений, которое будет иметь конкретное значение n. Используя стратегию, известную как «метод энтропии», Симкин изучил созданную им часть сетки (и назвал её «queenon»), чтобы найти значение верхней границы. Оба подхода используют усреднение и/или случайность как способ помочь смоделировать правильное значение. Симкин обнаружил, что две разные функции, которые он установил для значений нижнего и верхнего пределов, почти одинаковы — это означает, что пул возможных ответов очень тесно перемешан между ними, устанавливая надежную математическую оценку.
Вся эта тяжелая работа означает, что впервые с 1869 года имеется намёк на решение проблемы n ферзей. Для Симкина и его факультета в Гарварде это огромное достижение. Иронично то, что исследователь не играет в шахматы.