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

До 1995 года учёные считали, что теоретический минимум числа необходимых ходов равняется 18, но математику Майклу Риду (Michael Reid) удалось доказать, что существует позиция, требующая 20 перестановок. На проверку новой гипотезы ушло, как видим, около 15 лет.

В глубине души мы надеялись на то, что какая-нибудь комбинация, требующая 21 хода, всё же отыщется», — признаётся один из участников исследования Морли Дэвидсон (Morley Davidson) из Кентского университета штата (США).

Рис. 1. Гениальный венгерский изобретатель Эрно Рубик и его детище.

Общее число состояний кубика Рубика превосходит 43•10¹⁸ (точное значение — 43 252 003 274 489 856 000). Эта совокупность была разделена на 2,2 млрд групп, каждая из которых содержала 20 млрд позиций. После этого число групп уменьшили до 55 882 296: математики воспользовались тем, что изменение ориентации кубика в пространстве и отражение его в зеркале дают схожие позиции с аналогичными решениями.

«На рассмотрение одной такой группы хороший компьютер тратит 20–30 секунд», — говорит г-н Дэвидсон. Вычислениями должен был заняться суперкомпьютер, но исследователи воспользовались обычными машинами, предоставленными компанией Google, в которой работает один из авторов. Распределение нагрузки позволило за несколько недель выполнить все необходимые расчёты.

Как оказалось, число тех начальных позиций, которые требуют 20 ходов, сравнительно невелико; точную цифру учёные пока назвать не могут, а оценочная величина равна 300 млн. Подавляющее большинство вариантов головоломки решается за 15–19 ходов.

По материалам