Исследователи нашли самое короткое решение задачи кубика Рубика, на что потребовалось почти 30 лет.
Головоломка была изобретена в 1974 году венгерским архитектором Эрно Рубиком. К настоящему времени продано около 400 млн устройств. Самое быстрое решение принадлежит Эрику Аккерсдийку — 7,08 сек..
Всего общее число начальных позиций кубика Рубика – 43 квинтиллиона (миллиарда миллиардов). Для анализа всех таких комбинаций исследователи разбили 54 элемента кубика на 2,2 млрд групп, которые получили название «косетов», каждый из которых содержит 20 млрд комбинаций.
По словам профессора Дэвидсона, было бы совершенно безнадежным попытаться просчитать все группы. Поэтому исследователи сократили их число путем выявления дубликатов и используя теорию симметрии для выявления сходных комбинаций. Им удалось, в конце концов, сократить количество косетов до 56 млн.
На анализ каждого косета у хорошего настольного компьютера уходит 20–30 секунд. Это означало, что первоначально ученые решили воспользоваться суперкомпьютером. Но тут, по словам профессора Дэвидсона, на сцене появилась компания Google, которая предложила воспользоваться своим компьютерным парком, который состоит из тысяч соединенных между собой персоналок.
Исследователи пришли к выводу, что любая случайная комбинация составляющих элементов этого устройства может быть преобразована в одноцветные стороны за 20 и даже менее ходов. Полученный минимум в 20 ходов получил название «число Бога», поскольку всезнающее божество должно знать и оптимальное число комбинаций, необходимое для решения головоломки. «Мы знаем теперь наверняка, что это волшебное число равно 20», – заявил профессор Морли Дэвидсон, математик из Кентского государственного университета в штате Огайо.
До 1995 года эксперты полагали, что теоретическим минимумом ходов для кубика Рубика является число 18. Затем исследования математика Майкла Рида показали, что имеются начальные конфигурации, которые невозможно решить менее чем за 20 ходов. Однако профессор Дэвидсон считает, что эта цифра – чисто гипотетическая, потому что никому пока что не удалось обсчитать все возможные конфигурации.
«Кубик Рубика был в 1980-е годы, когда я был молод, очень популярен, и благодаря ему я и занялся математикой», – рассказывает профессор Дэвидсон.
По его словам, группа исследователей, которую он возглавляет, может теперь заняться решением подобной проблемы для более сложных версий головоломки Рубика в виде октаэдра или шара.
Нет записей, Ваша будет первой.