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

Алгоритмическая задача об одиночной карточной игре. Головоломка придумана известным британским математиком Джоном Х. Конвеем.

Условие задачи

Рассмотрим карточную игру для одного человека. У игрока 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⁶. Тогда общее количество строк CAT I SAW для всего ромба находится по формуле 4·2⁶ – 4. Четвёрку нужно вычесть, чтобы компенсировать избыточный подсчёт строк вдоль диагоналей ромба.

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

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

Не лучшим образом, в лоб, но решение. Для произнесения нам необходимо добраться от периферии к центру за буквой С и вернуться обратно. Ответом будет произведение количества путей до центра(А) и количества путей от центра(В). .Палиндром предполагает симметрию, а следовательно обратных путей будет столько же. А=В Нам нужно посчитать количество путей от периферии к центру. Обозначим финиш за единицу и графически подсчитаем количество путей из каждой точки на периферии. Результатом первого этапа будет сумма этих значений. получим 252. Ответ 252х252= 63504.

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