Рассмотрим следующую карточную игру (известную в Италии как «Cavacamicia», которую можно перевести как «полосатая рубашка»):

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

Игроки поочередно кладут в стопку следующую карту из своей колоды.

Если игрок (A) кладет вниз специальную карту, то есть I, II или III, другой игрок (B) должен последовательно положить соответствующее количество карт.

• Если при этом B кладет вниз специальную карту, действие меняется на противоположное и т. Д .; в противном случае, если B кладет соответствующее количество карт, но не имеет специальной карты, A собирает все снятые карты и добавляет их в свою колоду. А затем возобновляет игру, положив карту.

Первый игрок, у которого закончились карты, проигрывает игру.

Примечание: исход игры зависит исключительно от начального раздела колоды. (Что может сделать эту игру немного бессмысленной ;-)

Вопрос: эта игра всегда заканчивается? Что если мы обобщим эту игру и дадим любые две последовательности карт каждому игроку?

Относительно нищего соседа

Паулхус (1, с.164) писал в 1999 году:

$C$${D_{2}}^{'}(C)$

Но Конвей и соавт. (2, стр.892) писал в 2006 году:

Стриптиз-Джек-Голый или Нищий-Мой-Сосед ** 1

Еще одна проблема, на решение которой ушло почти 47 лет, касается этой старой детской игры. Каждый из двух игроков начинает с примерно половины карт (удерживаемых лицевой стороной вниз), которые они поочередно переворачивают на «стопку» на столе лицевой стороной вверх, пока один из них (который теперь является «командиром») сначала не раздаст одна из «командных карт» (валет, дама, король или туз).

После того, как один из них был сдан, другой игрок (теперь «ответчик») непрерывно переворачивает карты до ЛИБО. ** 2 появляется новая командная карта (когда игроки меняют роли ** 3) или, соответственно, 1, 2, 3 или 4 некомандных карты были перевернуты. В последнем случае командир переворачивает стек и присоединяет его к нижней части своей руки. Затем респондент начинает формирование нового стека, переворачивая свою следующую карту, и игра продолжается, как и прежде.

Игрок, который получает все карты, является победителем, и в реальных играх кажется, что кто-то всегда выигрывает. Интересный математический вопрос, заданный одним из нас много лет назад, был «действительно ли правда, что игра всегда заканчивается?» Марк Полюс недавно нашел ответ «нет!». Приблизительно 1 из 150 000 игр (сыгранных с обычными 52 картами) продолжается вечно.

Мы достаточно уверены, что ни один человек не играл в эту игру столько раз, так что шанс (со случайной перетасовкой) испытать игру без конца в игре за всю жизнь должен быть очень маленьким.

Тем не менее, точно также, однако, общее количество раз, когда в эту игру играли ** 4 детей в мире, должно быть значительно больше, чем 150 000, поэтому многие из них будут теоретически не прекращающими. Тем не менее, мы представляем, что на практике большинство из них действительно прекращают свою деятельность, потому что кто-то допустил ошибку.

К сожалению, я не смог найти в (2) какой-либо ссылки на открытие Паулюса ... Я хотел бы увидеть последовательность карт, которая дает игру без завершения, чтобы сказать, что проблема решена.

В 2013 году Лакштанов и Алексенко (3) написали:

Для карточных игр типа Beggar-My-Neighbor мы доказываем конечность математического ожидания продолжительности игры при условии, что игрок, играющий первую карту, выбирается случайным образом и что карты в колоде перемешиваются перед тем, как их кладут в колода. Результат также действителен для общих модификаций правил игры. Другими словами, мы показываем, что график цепочки Маркова для игры «Нищий-мой-сосед» поглощает; то есть из любой вершины есть хотя бы один путь, ведущий к концу игры.

но их правила не те, которым я следовал, когда играл в игру, когда был ребенком ;-)

Насколько мне известно, самая длинная игра «Нищий-мой-сосед» была найдена в 2014 году Уильямом Раклиджем с 7960 картами :

1: -J------Q------AAA-----QQ-
2: K----JA-----------KQ-K-JJK

Что касается Кавакамия

Я обычно играл в нее с колодой из 40 карт, а симуляции с половиной колоды (всего 20 карт) дают 16 игр без завершения в общей сложности 3,448,400 игр.

Список используемой литературы

(1) PAULHUS, Марк М. Нищий, мой сосед. Американский математический месяц , 1999, 162-165. http://www.jstor.org/stable/2589054

(2) BERLEKAMP, Elwyn R .; КОНВЕЙ, Джон Х .; ПАРЕНЬ, Ричард К. Пути победы в ваших математических играх, Том 4. AMC, 2003, 10: 12. http://www.maa.org/publications/maa-reviews/winning-ways-for-your-matumatic-plays -VOLUME-4

(3) ЛАКШТАНОВ Евгений Леонидович; АЛЕКСЕНКО, Алена Ильинична. Конечность в карточной игре Beggar-My-Neighbor. Проблемы передачи информации , 2013, 49.2: 163-166. http://dx.doi.org/10.1134/S0032946013020051