Ученый из гарварда (почти) решил 150 летнюю шахматную задачу.

Перевод статьи Джуана Силиезара

Ученый Михаил Симкин на протяжении почти пяти лет пытался решить задачу о ферзях пишет Гарвардская Газета и таки нашел решение.

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

Для обычной шахматной доски размером 8 на 8 клеток существует 92 таких расстановок. Но что если мы возьмем произвольную доску размером N на N клеток и попытаемся разместить N ферзей? Например 1000 ферзей на доску размером 1000 на 1000 клеток? Или миллионы ферзей на пропорционально огромную доску?

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

Михаил Симкин, подсчитал, что существует примерно (0,143N)^N способов расставить n ферзей на доске размером N на N при больших N. Насколько больших? Стремящихся к бесконечности.

Уравнение Симкина не дает точное решение, а вместо этого предлагает приблизительное число, наиболее близкое к настоящему ответу. Число 0,143, представляющее собой средний уровень неуверенности в конечном значении, умножается на какое-то число N и потом возводится в степень N, и так ты получаешь ответ.

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

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

«Если бы вы сказали мне, что я хочу, чтобы вы расставили своих ферзей на доске таким-то и таким-то образом, я бы смог проанализировать алгоритм и сказать вам, сколько существует решений, соответствующих этому ограничению», — говорит Симкин «Формально это сводит проблему к задаче оптимизации».

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

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

Симкин работал над проблемой N ферзей почти пять лет. Он говорит, что лично он ужасный шахматист, но стремится улучшить свою игру. «Мне все еще нравится играть, но, думаю, математика более снисходительна» — говорит Симкин.