ШишНашКи
Что тут? Математическая головоломка, немножко групповых перестановок, две задачи для узколобых и грань шутки. Beg your pardon, если эта головоломка придумана до меня и я жалкий невежа, вообразивший, что изобрел нечто новенькое. В случае лицензионной чистоты я нарекаю её ШишНашКи отныне и вовеки веков. Аминь.
По следам публикации
Человеческий гений в лице Mrrl решил задачу Бога в уме за 20 ходов.
Видео решения
Постановка задачи
Дана доска 4x4 клетки со случайно перемешанными числами от 1 до 16.
Случайный расклад
Перестановками необходимо упорядочить все клетки по возрастанию, начиная с верхнего левого угла доски. Перестановкой называется вращение любых 4 соседних клеток на пи, 2*пи и минус пи.
Пример перестановки в математической записи (поворот на -пи нижнего правого угла):
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16
01 02 03 04 05 06 07 08 09 10 15 11 13 14 16 12
Головоломка чем-то напоминает Кубик Рубика, но есть нюансы. Нет групп симметрии (я не буду вдаваться в подробности математической теории КР). И любой из 16! раскладов решается. Эту теорему достаточно легко доказать, решив задачу номер 1.
Задача номер 1
Найдите комбинацию перестановок, меняющих местами две голубые клетки.
Расклад задачи номер 1
-U-M-L+U+L
Задача номер 2
Найти число Бога для этой головоломки. Число Бога — это минимальное число ходов, с помощью которых решается любой расклад. Например, для Кубика Рубика, в 2008 году это число было 23, а ныне — уже 20. Проблему решили перебором всех раскладов. Моя задача попроще, но также не сахар: 16 — не хрен собачий, скажите спасибо, что автор не выбрал доску 5x5.
Я решил, что наихудший расклад из всех возможных — полная инверсия доски. В этом случае каждую клетку надо тянуть через все поле.
Начальный наихудший расклад
Несколько помучившись и стартовав от числа Бога=39, я дошел до 30.
Фейковая таблица рекордов в достижении числа Бога
Думаю, на Хабре есть пара человек, которые найдут число Бога, равное 25. Ну хорошо, хорошо, Mrrl, не два, а три человека.
Кто хочет поиграться на iPhone, игра готова для бесплатного тестирования. С Вас — apple id.
