Кубик Рубика
Кубик Рубика – одна из самых популярных игрушек в истории. Это также пример перестановочной головоломки, которые изучаются математиками в той или иной форме уже более 150 лет. Учитывая математическую сложность, становится странно, насколько популярным стал кубик Рубика. Положа руку на сердце, очень не многие люди признаются, что сами собрали его. Потому что очень мало кто сам собрал эту головоломку, и может быть чуть больше людей собрали его при помощи подсказок в книге или в интернет. Сам Эрнё Рубик (венгерский скульптор и преподаватель архитектуры, изобретатель кубика) потратил несколько недель для решения своей головоломки.
Сейчас кажется удивительным, что спустя почти 40 лет после 1980 года, люди все еще интересуются кубиком Рубика и исследуют его. Например, математики Морли Дэвидсон (Morley Davidson) и Томас Рокики (Tomas Rokicki) в 2015 году показали, что число Бога кубика Рубика равно 20. Свои вычисления они проводили с помощью суперкомпьютера.
Почему суперкомпьютер. А потому что у всем известного кубика Рубика 43 миллиарда миллиардов возможных состояний (43 в степени 1019). Теперь вы понимаете, почему эта головоломка сложная. Хотя число комбинаций просто огромно, но оно конечно. Поэтому существует наихудший сценарий, наиболее сложная и запутанная позиция.
Число Бога – это, наименьшее число ходов, которые потребуются Богу или суперкомпьютеру (в нашем случае), чтобы сложить кубик Рубика из «наихудшей ситуации». Другими словами, кубик Рубика можно собрать из любого положения за 20 шагов или меньше.
Обычный компьютер не может решить такую трудоемкую задачу. Девидсон и Рокики сократили количество комбинаций до нескольких миллиардов. А после уже закончили вычисления на суперкомпьютере Ohio Supercomputer Center. На вычисления было потрачено примерно 32 CPU-года, которое было предоставлено им компанией Google.
Пятнашки (15-puzzle)
Перестановочные головоломки намного старше кубика Рубика, они пришли к нам из древности. Еще один пример, всем известная игра «пятнашки» (15-puzzle). Настоящий бум «пятнашек» пришелся на 1880 год в Соединенных Штатах Америки, почти за 100 лет до изобретения кубика Рубика.
Сэм Лойд (Sam Loyd), которого одни называли популяризатором науки, гением, а другие торгашом и заклинателем змей, даже предложил 1000$ любому, кто сможет поменять местами только 2 фишки 15 и 14, когда все остальные фишки уже заняли свои места. Он скорее всего был уверен, что это невозможно. А возможно, даже знал, что эта теорема уже была доказана математиками Уолси Джоносоном (Wm. Woolsey Johnson) и Уильямом Стори (William E. Story) в 1879 году.
Стомахион (Stomachion)
А самая древняя перестановочная головоломка, которую мы знаем это Стомахион (Stomachion). Стомахион – это рассечение квадрата на 14 частей с помощью прямых линий. После рассечения, если эти фигуры все вытащить, то снова сложить их обратно в квадрат, бывает очень сложно.
Стомахион привлек внимание величайшего математика древнего мира Архимеда. Он даже написал трактат об этой загадке. Сам трактат был утерян, но позже часть его была восстановлена в палимпсесте. В трактате Архимед ставит задачу найти количество различных способов собрать все 14 частей снова в квадрат. Вычислил ли Архимед это, мы не знаем. Однако, математик Бил Катлер (Bill Cutler) сумел это подсчитать. Он получил, что существует 17 152 способа сложить стомахион. Если Архимеду удалось выполнить это вычисление, то основная загадка в том, как именно он это сделал без компьютера.
