Вчені розкрили секрет кубика Рубіка

71
12 серпня 2010

Науковцям таки вдалося майже через 30 років пошуків знайти найкоротшого рішення задачі кубика Рубіка.

Дослідники прийшли до висновку, що будь-яка випадкова комбінація складових елементів цього пристрою може бути перетворена в одноколірні сторони за 20 і навіть менше ходів, пише ВВС.

Міжнародна група експертів скористалася комп'ютерним парком компанії Google: тут перебиралися всі можливі комбінації 54 кольорових квадратів, з яких складена механічна головоломка - кубик Рубіка.

Отриманий мінімум в 20 ходів отримав назву "число Бога", оскільки всезнаючі божество має знати і оптимальне число комбінацій, необхідний для вирішення головоломки.

"Ми знаємо тепер напевно, що це чарівне число дорівнює 20", - заявив професор Морлі Девідсон, математик з Кентського державного університету в штаті Огайо.

Всього загальна кількість початкових позицій кубика Рубіка - 43 квінтильйонів (мільярди мільярдів). З них, як показали обчислення, існує більше 100 тисяч позицій, які можуть бути вирішені за 20 ходів. Проте більшість цих рішень може бути досягнуто за 15-19 ходів.

До 1995-го року експерти вважали, що теоретичним мінімумом ходів для кубика Рубіка є число 18. Потім дослідження математика Майкла Ріда показали, що є початкові конфігурації, які неможливо вирішити менше ніж за 20 ходів.

Проте професор Девідсон вважає, що ця цифра - суто гіпотетична, тому що нікому поки що не вдалося обрахувати всі можливі конфігурації.

Для аналізу всіх таких комбінацій дослідники розбили 54 елемента кубика на 2,2 мільярди груп, які отримали назву "косетов", кожен з яких містить 20 мільярдів комбінацій.

За словами професора Девідсона, було б абсолютно безнадійним спробувати прорахувати всі групи. Тому дослідники скоротили їхнє число шляхом виявлення дублікатів і використовуючи теорію симетрії для виявлення схожих комбінацій. Їм вдалося, врешті-решт, скоротити кількість косетов до 56 мільйонів.

На аналіз кожного косета у хорошого настільного комп'ютера йде 20-30 секунд. Це означало, що спочатку учені вирішили скористатися суперкомп'ютером. Але тут, за словами професора Девідсона, на сцені з'явилася компанія Google, яка запропонувала скористатися своїм комп'ютерним парком, що складається з тисяч з'єднаних між собою персоналок.

"Кубик Рубіка був у 1980-ті роки, коли я був молодий, дуже популярним, і завдяки йому я і зайнявся математикою", - розповідає професор Девідсон.

За його словами, група дослідників, яку він очолює, може тепер зайнятися рішенням подібної проблеми для більш складних версій головоломки Рубіка у вигляді октаедра або кулі.

powered by lun.ua