Карточная головоломка Конвея

Карточная головоломка Конвея

Рассмотрим карточную игру для одного человека. У игрока 13 карт одной масти. Каждой карте присвоено числовое значение. Туз, валет, дама, король соответствуют 1, 11, 12 и 13. Перед началом игры карты перемешиваются. Далее циклически повторяется следующая операция.

Поднимается верхняя карта колоды. Если это туз, игра останавливается. В противном случае (если N != 1 ), N карт, включая поднятую, снимаются с колоды и вновь кладутся сверху, но в обратном порядке.

Пример шага игры:

5 7 10 K 8 Т 3 Д В 4 9 2 6 ⇒ 8 K 10 7 5 Т 3 Д В 4 9 2 6

Вопрос: Всегда ли игра останавливается после конечного числа итераций для любого начального состояния колоды? Объясните свой ответ.

Эта задача – двенадцатый эпизод нашего сериала головоломок. После описания задачи идёт ответ на предыдущую загадку Чеширского Кота.

Решение загадки Чеширского Кота

Ответ: 63504.

Решение. Нужно учесть симметрию ромба и начать с подсчёта количества способов написания подстроки CAT I SAW . Любая такая строка начинается в центре буквы С и содержится в одном из четырёх треугольников, разделенных диагоналями ромба. Один из этих треугольников показан ниже на рисунке.

Карточная головоломка Конвея

Количество строк CAT I SAW в треугольнике можно найти с помощью стандартного метода динамического программирования. Мы использовали его в одной из предыдущих задач.

Чтобы найти все пути, нужно двигаться от катетов треугольника к гипотенузе. Можно видеть, что эти числа образуют треугольник Паскаля. Сумма чисел на гипотенузе треугольника (границе ромба) равна 2 6 . Тогда общее количество строк CAT I SAW для всего ромба находится по формуле 4·2 6 – 4. Четвёрку нужно вычесть, чтобы компенсировать избыточный подсчёт строк вдоль диагоналей ромба.

Это означает, что общее количество способов прочтения палиндрома WAS IT A CAT I SAW составляет (4·2 6 – 4) 2 = 63504.

Как ответили читатели Библиотеки программиста? Слегка другим путём (без учёта симметрии), но к тому же результат пришёл пользователь randomadman:

Карточная головоломка Конвея

На поясняющем рисунке можно видеть тот же треугольник, что получился в нашем решении.