Ученые сложили кубик Рубика

0

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

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

Общее число состояний кубика Рубика — 43.252.003.274.489.856.000. Эта совокупность была разделена на 2,2 млрд. групп, каждая из которых содержала 20 млрд. позиций. После этого число групп уменьшили до 55.882.296: математики воспользовались тем, что изменение ориентации кубика в пространстве и отражение его в зеркале дают схожие позиции с аналогичными решениями.

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

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

Поделиться.

Комментарии закрыты