Математик Михаил Симкин из Центра математических наук и приложений Гарвардского университета утверждает, что ему удалось решить известную комбинаторную задачу о ферзях в обобщенном виде, которой уже более 150 лет, пишет издание Quanta Magazine. Соответствующая статья выложена на сайте электронных препринтов arXiv.org и пока еще не прошла полноценную проверку другими математиками.

источник: d2r55xnwy6nx47.cloudfront.net

В исходном виде на стандартной 64-клеточной шахматной доске задача требует расстановки 8 ферзей так, чтобы ни один из них не находился под боем другого. Обобщенная задача — расстановка ферзей на произвольном поле прямоугольной формы, в частности, на квадратном шахматном поле со стороной n. Для стандартной шахматной доски и 8 ферзей существует 92 подходящие конфигурации, а обобщенную задачу в математическом виде можно сформулировать как требование заполнить матрицу размерностью n нулями и единицами таким образом, чтобы сумма всех ее элементов была равна n, но при этом ни в одном столбце, строке или диагональном ряде матрицы сумма элементов не превышала единицы, а затем ответить на вопрос, сколько всего существует вариантов подобного заполнения.

Симкину, по его утверждению, удалось доказать, что для больших шахматных досок с соответствующим количеством ферзей существует примерно (0,143n)n конфигураций. На доске размером миллион на миллион количество способов расставить миллион ферзей, не представляющих угрозы друг для друга, составляет примерно единицу с пятью миллионами нулей.

Первоначально головоломка появилась в немецком шахматном журнале в 1848 году, а обобщенная задача была сформулирована в 1869 году. С тех пор математики обращались к этой задаче множество раз, но решение получали с помощью перебора вариантов компьютером. Симкин же впервые смог получить этот результат чисто математическими методами.

Четыре года назад Симкин совместно с математиком Цуром Луриа из Швейцарской высшей технической школы Цюриха уже решил более простую версию задачи размещения ферзей на «тороидальном» поле размерностью n. В этой модифицированной версии шахматная доска «обвивается» вокруг себя как тор: при движении за край вправо ферзь снова покажется из-за края слева. В отличие от классической доски, все диагонали на такой доске имеют одинаковую длину, и каждый ферзь может атаковать одинаковое количество клеток.