Шулеры, или Математическое исследование одной карточной игры

3

Государственное учреждение образования

«Средняя школа № 41 г. Минска»

ШУЛЕРЫ, или МАТЕМАТИЧЕСКОЕ ИССЛЕДОВАНИЕ

ОДНОЙ КАРТОЧНОЙ ИГРЫ

Задворный Ярослав Борисович,

учащийся 11 класса

ГУО «Средняя школа № 41 г. Минска»

Минск, 2009

ОГЛАВЛЕНИЕ

§1. Введение

1.1. Исходная постановка задачи

1.2. Основные определения и обозначения

§2. Основные результаты для игры с двумя игроками

2.1. Решение начальной задачи

2.2. Количества правильных игр

2.3. Классы эквивалентности

2.4. Преобразования конечных двоичных последовательностей

§3. Игра для двух игроков

§4. Заключение

§1. Введение

Теория игр - разветвленная область математических исследований, связанная своими результатами и методами с различными направлениями современной дискретной математики (алгоритмика, теория графов, комбинаторика, теория чисел, криптография, теория кодирования, алгебра и др.). Данная работа посвящена исследованию одного класса карточных игр для одного или более игроков.

1.1 Исходная постановка задачи

Исходная постановка для одного игрока: п карт расположены по окружности картинкой вниз (состояние 0). За один ход разрешается взять любую неперевернутую карту, отсчитать от нее k-ю по часовой стрелке карту (считая исходную карту нулевой) и перевернуть ее, если она неперевернута (перевести в состояние 1). При заданных п и k требуется найти алгоритм, играя по которому, можно перевернуть максимально возможное число карт (для этих п и k)?

1.2 Основные определения и обозначения

Игра - это последовательность ходов, переводящая исходное состояние в конечное

п - длина игры, k - длина хода

(п, k) - обозначение игры длины п с ходом k

НОД(n,k) = d(n,k)

Ход П^+k - ход, при котором берётся некоторая неперевёрнутая карта, отсчитывается k-ая от неё по часовой стрелке и переворачивается (т.е. вторая карта перевёрнута от первой)

Ход П^-k - ход, при котором берётся некоторая неперевёрнутая карта, отсчитывается k-ая от неё против часовой стрелки и переворачивается

Простая игра - последовательность ходов, после которых остаётся неперевёрнутой одна карта

Правильная игра - игра, в результате которой неперевёрнутыми остаётся наименьшее возможное при данных n и k количество карт.

Игра первого типа (типа А) - это игра при которой разрешены ходы только типа П^+k

Игра второго типа (типа В) - это игра, при которой разрешены ходы типов П^+k и П^-k

Компонента - это совокупность карт такая, что никакая карта, не принадлежащая этой совокупности, не может быть перевёрнута ни от одной из карт этой совокупности, и ни одна карта этой совокупности не может быть перевёрнута ни от одной карты, не принадлежащей этой совокупности. При этом компонента может содержать несколько других непересекающихся между собой компонент, более точно: состоять из нескольких других компонент меньшей длины. Если единственная компонента, которую она содержит - это сама эта компонента, то такая компонента называется простой.

Утверждение 1: Если длина простой компоненты равна p, то игра (p,k) является простой.

Круг(n,k) - это совокупность из n карт, расположенных по окружности, если нам разрешён ход П^+k и(или) ход П^-k. Ряд карт - это несколько подряд идущих неперевёрнутых карт.

Две игры (п,k) и (п, т) эквивалентны, если существует перестановка карт одной из этих игр, в результате которой получается вторая игра.

Два круга эквивалентны, если существует перестановка карт одного из них, в результате которой получается другой круг.

Утверждение 2: Две игры (п,k) и (п, т) эквивалентны, если при правильной игре любого типа в обеих играх остаётся одинаковое число карт.

§2. Основные результаты для игры с двумя игроками

2.1 Решение начальной задачи

Условие начальной задачи. 10 карт расположены по окружности картинкой вниз. Мы можем взять любую неперевёрнутую карту (неперевёрнутыми считаем карты, лежащие картинкой вниз), отсчитать от неё третью по часовой стрелке карту (считая исходную карту нулевой), и перевернуть её, если она не перевёрнута. Требуется указать алгоритм, играя по которому, можно оставить неперевёрнутой только одну карту (т.е. необходимо найти простую игру). Требуется также подсчитать количество всевозможных простых игр.

Решение. 1) Пронумеруем карты числами от 1 до 10 по часовой стрелке.

Теперь заметим, что игра на круге (10,3) эквивалентна игре на круге (10,1). Чтобы убедиться в этом, переложим карты следующим образом:

1 4 7 10 3 6 9 2 5 8

В итоге получаем круг (10,1), т.к. карта №4 переворачивается от карты №1, карта № 7 - от карты № 4 и т.д.

Заметим, что какую карту мы перевернём первой, значения не имеет. Будем считать, что сначала мы перевернули карту №1 (будем обозначать жирным шрифтом номера уже перевёрнутых карт):

1 4 7 10 3 6 9 2 5 8

Теперь, пусть мы перевернули какую-либо карту, кроме № 8. Тогда оставшиеся неперевёрнутыми карты разобьются на две компоненты:

1 4 7 10 3 6 9 2 5 8

(Мы подчеркнули те карты, которые принадлежат одной из двух компонент, если на втором ходу была перевернута карта № 6)

Описанную перестановку будем впоследствии называть перестановкой типа Р₃ (в общем случае - P_k, в зависимости от длины хода).

По определению компонент ясно, что в каждой компоненте останется неперевёрнутой хотя бы одна карта, а значит, перевернуть все карты, кроме одной, мы не сможем. Мы попадаем в такую ситуацию, если переворачиваем любую карту, кроме карты № 8 (карту № 4 мы перевернуть не можем, так как она может быть перевёрнута только от уже перевёрнутой карты № 1). Значит, вторым ходом мы вынуждены перевернуть карту № 8.

Далее, третьим ходом мы по аналогичным причинам можем перевернуть только карту № 5, четвёртым - только карту № 2 и далее карты № 9, № 6, № 3, № 10 и № 7. Таким образом, в конце остаётся одна карта № 4.

Таким образом:

Утверждение 3. На круге (10,3) существует правильная простая игра первого типа.

Утверждение 4. Количество простых игр первого типа - 1.

2) Пусть нам разрешён не только ход П⁺⁴, но и ход П^-4.

Пусть опять-таки мы пронумеровали все карты числами от 1 до 10, аналогично предыдущему пункту свели игру на круге (10,3) к игре на круге (10,1) и первым ходом перевернули карту № 1. Тогда следующим ходом (по тем же причинам, что и раньше) можем перевернуть только карту №8 либо карту № 4. На третьем ходу у нас снова будет два варианта для хода и т.д. Итого мы получим, что всего у нас 2⁸ =256 игр. (Мы сделали 9 ходов, первый из которых не учитывается, а на остальных восьми мы имели по 2 варианта для хода).

Утверждение 5. Количество простых игр второго типа - 2⁸=256

Далее, пусть мы играем на круге (n,k).

Пусть n не взаимно просто с k. Тогда нетрудно убедиться, что такой игры попросту не существует, так как карты изначально разбиваются на компоненты (такие же, как в п.1.2)

Покажем это на примере, когда n = 10 и k = 2:

1 2 3 4 5 6 7 8 9 10

Как и раньше, мы подчеркнули карты, принадлежащие одной из двух компонент.

Если же n взаимно просто с k, то компонент не будет (или, иными словами, компонента будет только одна). Тогда аналогично предыдущим пунктам можем установить, что в случае а) ответ 1, а в случае б) ответ 2^n-2.

Также мы можем определить наименьшее количество карт, которое может остаться неперевёрнутыми, при любых n и k. Легко видеть, что мы не сможем перевернуть по крайней мере по одной карте в каждой компоненте, но оставить ровно одну неперевёрнутую карту в каждой компоненте мы можем. (Вспомним случай, когда n = 10 и k = 3. По сути, все 10 карт представляют собой простую компоненту. В данном случае мы в любой отдельной части сможем перевернуть все карты, кроме одной, по тому же алгоритму). Таким образом, наименьшее количество карт, которое мы сможем оставить неперевёрнутыми, равно количеству компонент. А количество компонент равно d(n,k). Таким образом, при любых n и k мы сможем оставить неперевёрнутыми d(n,k) карт.

Сформулируем сказанное выше в виде следующих утверждений.

Теорема 1. Игра (n,k) является простой тогда и только тогда, когда d(n,k)=1.

Теорема 2. Игру (n,k) можно разбить на d(n,k) простых компонент.

Следствие. Количество карт, которые останутся неперевёрнутыми при правильной игре типа А или В равно d(n,k).

2.2 Количество правильных игр

Определим количество правильных игр при произвольных n и k. Пронумеруем карты числами от 1 до n.

а) (Разрешены только ходы П^+k) Как мы уже доказали, в каждой компоненте останется неперевёрнутой одна карта. Сколькими способами мы можем определить эти d(n,k) карт? Легко понять, что искомое количество способов равно (n/d(n,k))^d(n,k), где n/d(n,k) - это количество карт в каждой компоненте, а d(n,k) - количество компонент. Далее, сколькими способами мы можем перевернуть все остальные карты? Всего есть (n - d(n,k))! способов перевернуть в произвольном порядке n - d(n,k) карт (а именно столько карт нам нужно перевернуть). В каком порядке переворачиваются карты, принадлежащие разным компонентам, нас не беспокоит - все компоненты вообще «живут» независимо друг от друга. Что же касается совокупности карт из одной компоненты, то здесь это не так. Для любой отдельно взятой компоненты есть только одна игра, по которой мы сможем перевернуть все карты, кроме одной (количество игр равно 1, а не количеству карт в части, так как мы предопределили ту карту, которую хотим оставить неперевёрнутой), а мы посчитали эту игру за (n/d(n,k)-1)! игр ((n/d(n,k)-1) - это количество карт, которое мы должны перевернуть в каждой группе). С учётом того, что мы предопределили номера всех перевёрнутых карт, а также того, что мы учитывали номер карты, которую перевернём первой, количество всевозможных игр равно

.

б) (Разрешены и ход П^+k, и П^-k) Как мы уже доказали, в каждой компоненте останется неперевёрнутой одна карта. Как и в пункте а), мы можем определить номера этих карт (n/ d(n,k))^d(n,k) способами. Сколькими способами мы можем перевернуть все остальные карты в этом случае? Как и ранее, всего способов перевернуть n - d(n,k)) карт есть (n- d(n,k))!. А сколько возможных игр есть для одной компоненты? Мы посчитали, что таковых (n/ d(n,k))-1)!, хотя на самом деле их 2(в обычном случае их 2^n-2; в обычном случае мы не учитывали, какую карту переворачиваем первой, в рассматриваемом нами нам небезразлично, какую карту перевернуть первой, но безразлично, какую - последней (точнее, карта, которую мы перевернём последней, предопределена), значит, общее количество игр и в обычном, и в данном случае одинаково и равно 2^n-2). А учитывая, что мы предопределили номера всех неперевёрнутых карт и учитывали номер карты, которую перевернули первой, получаем искомую формулу:

.

2.3 Классы эквивалентности

Дадим ещё одно определение эквивалентных игр, которое равносильно определению п. 1.2.

Две игры (n,k) и (n,т) назовем эквивалентными, если количества карт, оставшихся неперевернутыми при правильной игре типа А (или Б) одинаковы.

Класс эквивалентности игр длины п - множество игр длины п, попарно эквивалентных дуг другу.

Теорема 3. Игры (n,k) и (n,т) эквивалентны тогда и только тогда, когда d(n,k) = d(n,m).

Следствие. Количество классов эквивалентности, на которые разбиваются все игры (n,k), где n фиксировано, а k<n, равно количеству делителей числа п, не равных п. Заметим, что числа k и m принадлежат одному классу эквивалентности тогда и только тогда, когда круги (n,k) и (n,m) содержат одинаковое количество простых компонент. То, что они обязаны содержать одинаковое количество простых компонент, очевидно. Теперь, пусть круги (n,k) и (n,m) содержат одинаковое количество простых компонент. Легко видеть, что игра на простой компоненте эквивалентна игре на круге (x,1), где x - количество карт в компоненте (с любой простой компонентой мы можем сделать то же, что выше сделали с кругом (10,3), который и сам представляет из себя простую компоненту). Кол-ва карт в двух простых компонентах одного круга равны, т.е. легко видеть, что, если круги (n,k) и (n,m) содержат одинаковое количество простых компонент, игра на них эквивалентна. Мы уже говорили, что количество простых компонент, на которые разбит круг (n,k), равно d(n,k). Значит, теорема доказана.

Классы эквивалентности при n = 10:

L_(10,1):{(10,1);(10,3);(10,7);(10,9)}.

L_(10,2):{(10,2);(10,4);(10,6);(10,8)}.

L_(10,5): {(10,5)}.

Теорема 4. |L_(n,k)|=ц(n/d(n,k)), то есть мощность класса эквивалентности, определённого игрой (n,k), равно ц(n/d(n,k)).

(Класс эквивалентности определён игрой (n,k), если k - такой делитель n, что игра (n,k) принадлежит данному классу эквивалентности)

2.4 Преобразования конечных двоичных последовательностей

Пусть по окружности в некотором порядке расположены n единиц и нулей (исходное состояние S₀). Некоторые нули разрешается заменять на единицы в соответствии с правилами игры (n,k) (пп. 1.1-1.2.).

1) При каких условиях из произвольной последовательности S₀ можно получить последовательность, состоящую из одного нуля и n-1 единицы?

2) При каких условиях мы можем получить последовательность, состоящую из t = d(n,k) единиц?

Две конечные последовательности эквивалентны, если обе при правильной игре типа А или В приводятся к одной и той же конечной последовательности нулей и единиц.

Теорема 5. Если при перестановке типа P_k из последовательности S₀ получится двоичное число (2^p-1)2^q, где 0 ? p+q ? n, то последовательность S₀ эквивалентна последовательности (1,1,…,1,0)

Теорема 6. Если при перестановке типа P_k из последовательности S₀ получится двоичное число вида ((2^p_j-1)2^q_j)2^k_j, где 0 ? p+q ? n/d, то последовательность S₀ эквивалентна последовательности (111…110111…1110). (d отрезков последовательности, каждый из которых состоит из -1 единиц и одного нуля)

Теорема 7. Последовательность S₀ мы можем получить из нулевой последовательности тогда и только тогда, когда ни одна компонента последовательности S₀ не состоит из одних единиц.

Доказательство теоремы 5. Если перестановка P_k имеет вид 00…00111…111000, то метод, по которому все остальные нули, кроме одного, превращаются в единицы, описан в п. 2.1. Из того же пункта можно видеть, что перестановки типа P_k другого вида к искомой последовательности не приводится.

Теорема 6 доказывается аналогично.

Доказательство теоремы 7. Докажем сначала для k=1.

Пронумеруем числа (как на исходном кругу, так и на нулевом кругу) числами от 1 до n по часовой стрелке. Пусть k-ое число на исходном кругу - нуль. Тогда будем двигаться по нулевому кругу, взяв за начало движения k-ый нуль и двигаясь против часовой стрелки, и будем рассматривать каждый встречающийся нам нуль. Пусть сейчас мы рассматриваем m-тый нуль. Тогда, если m-тое число на исходном кругу - единица, заменим на нулевом кругу m_тый нуль единицей (мы можем это сделать, т.к. m-1-ое число на нулевом кругу на данной стадии нуль). Таким образом, обойдя нулевой круг, мы превратим его в исходный.

Исключение составляет случай, когда исходный круг состоит из одних единиц (то, что мы не можем получить такой круг, мы уже доказали - аналогичное утверждение доказывалось нами при рассмотрении карточной задачи).

При k > 1 утверждение доказывается аналогично.

§3. Игра для двух игроков

Пусть на круге (n,k) играют два игрока. Они делают ходы по очереди. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре?

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

Пусть наша компонента имеет вид круга (x,y) (мы помним, что каждая простая компонента имеет вид круга). Тогда уже описанным выше способом превращаем этот круг в круг (x,1). (Вспомним, как мы превращали круг (10,3) в круг (10,1). Заметим, что в этой игре безразлично, есть ли возможность хода П^-1 или есть только возможность хода П⁺¹. Ведь каждый ход - это есть разбиение какого-то ряда подряд идущих неперевёрнутых карт на два таких ряда (или, может быть, уменьшение количества подряд идущих карт в некотором ряду на одну, если будет перевёрнута одна из крайних карт ряда). Цель обоих игроков в обоих случаях одна и та же - получить после своего хода позицию, при котором не найдётся ряда подряд идущих неперевёрнутых карт длиннее одной карты. Даже то, что в одном из случаев игроки не могут переворачивать первую карту в ряду, ничего не меняет - ведь они могут перевернуть последнюю, что по сути приведёт к тому же положению. Поэтому оба случая идентичны. Будем рассматривать случай, в котором ход П^-1 возможен, так как он кажется нам более красивым.

Пронумеруем карты на круге числами от 1 до х.

При четных х выигрывает второй - он попросту играет симметрично ходам первого игрока. Исключение составляет случай х=2, в котором, естественно, выигрывает первый.

При нечётных х мы имеем гипотезу, что первый игрок выигрывает при х = 8m + 5, а при прочих х выигрывает второй. К сожалению, эта гипотеза пока не доказана. Мы предлагаем несколько нечётных значений х, при которых наша гипотеза доказана.

Заметим, что какую карту первым ходом перевернёт первый игрок, значения не имеет. Поэтому будем считать для удобства, что первой он переворачивает карту № x.

При х=3 очевидно, что выигрывает второй игрок.

При х=5 почти так же очевидно, что выигрывает первый. Первый его ход, как уже было сказано, ничего не меняет; легко видеть, что на любой первый ход второго игрока первый сможет ответить так, что игра тут же закончится (у второго не будет хода).

Будем показывать выигрышную стратегию для какого-либо игрока при помощи таблицы. После первого хода первого игрока круг из 5 карт превращается в ряд из четырёх:

1	2	3	4
3	4	1	2

Число в верхней строке таблицы обозначает номер карты (будем считать для удобства, что своим первым ходом первый игрок переворачивает карту с номером х, т. е. в данном случае с номером 5). Поясним, что означает число в нижней строке. Пусть второй игрок своим первым ходом перевернул карту №1. Видим, что в нижней строке таблицы в графе карты №1 стоит цифра 3. Это значит, что своим вторым ходом первый переворачивает карту под номером 3. Легко видеть, что тогда он выигрывает (у второго нет хода). Т. е. число в нижней строке обозначает своеобразный «ответный победный ход», в данном случае, для первого игрока.

Легко видеть, что если второй игрок перевернёт своим первым ходом карту №2, то ответный ход, которым первый (в соответствии с таблицей) перевернёт карту №4, будет для него победным и т.д., т.е. при х = 5 первый выигрывает.

Пусть х=7. Как мы договаривались, первый игрок первым ходом переворачивает карту №7. В ответ второй переворачивает карту №2. Карта №1 как бы выбывает из игры, и игра продолжается на картах с №3 по №6. Этот случай (т.е. случай при игре на ряде из четырёх картах) уже был рассмотрен выше. Видим, что выигрывает второй.

При х=9 выигрывает второй, перевернув своим первым ходом третью карту:

1	2	3	4	5	6	7	8
4	4		1	6	5	6	1

Случаи, когда своим следующим ходом переворачивает карту №1, №2, №4 или №8 (а второй - соответственно №4 или №1), приводят к уже рассмотренному нами варианту. Остальные случаи приводят к игре на двух рядах по две карты в каждом (будем называть рядом совокупность подряд идущих неперевёрнутых карт), и после двух следующих ходов игра окончится победой второго игрока.

При х=11 второй игрок своим первым ходом переворачивает четвёртую карту и выигрывает:

1	2	3	4	5	6	7	8	9	10
5	6	5		3	2	6	9	2	1

Случаи, когда первый игрок следующим ходом перевернул карту №1, №2, №3, №5, №6, №9 или №10 (а второй игрок ответил соответственно таблице), приводят к уже рассмотренным нами вариантам. В остальные случаях игра продолжается на двух рядах по три карты в каждом, и второй игрок выиграет, если будет играть симметрично ходам первого игрока.

При х=13 выигрывает первый игрок:

1	2	3	4	5	6	7	8	9	10	11	12
7	6	4	8	9	12	1	4	5	3	7	6

Случаи, когда второй игрок своим первым ходом перевернет карту №1, №6, №7 или №12, приводят к позициям, когда первый может выигрывать при помощи симметрии. Если второй перевернёт карту №4, №5, №8 или №9, то после ответа первого игра будет продолжаться на двух рядах по три карты (на которых первый будет играть симметрично второму) и на ряд из четырёх карт, на котором также выиграет первый (соответственно рассмотренному выше случаю для ряда из четырёх карт). Если второй следующим ходом перевернёт карту №2 (или карту №11 - два симметричных случая) а первый следующим ходом, соответственно, №6, то игра продолжится на двух рядах из 3 и 6 карт, который уже был рассмотрен выше (случай х=11)

Если же следующим ходом второй перевернул карту №3 (или №10), а первый ответит соответственно таблице, то дальнейшая игра первого может быть такова:

1	2	3	4	5	6	7	8	9	10	11	12
7	7			7	7	1	7	10	1	10	10

Ходы второго, переворачивающие карты №1, №2, №5, №6, №7, №10, №11, №12, приводят к уже рассмотренным нами случаям; если второй перевернёт карту №8 или №9, то игра продолжается на двух рядах по две карты и на одном - из четырёх карт. Первый игрок будет играть за второго отдельно на двух рядах по две карты и отдельно - на ряду из четырёх карт, в обоих случаях он выиграет.

При х=15 второй попросту переворачивает карту №2, после чего играет на ряде из 12 карт по уже описанному выше алгоритму.

При х=17 своим первым ходом второй переворачивает карту №7:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
8	12	14	14	12	8		6	10	13	14	5	10	3	14	6

Случаи, когда следующим ходом первый переворачивает одну из карт №2, №3, №4, №5, №10, №11, №12, №13 или №14, затруднений не вызывают. В результате игра продолжается на трёх рядах по 4 карты (на всех трёх второй выигрывает так же, как он выигрывал на одном в случае х = 5) либо на двух рядах по 2 карты (на этих двух рядах воспользуемся симметричной игрой), на ряде из 3 и ряде из 6 карт (игра на двух рядах - из 3 и 6 карт - уже была рассмотрена выше). Если следующим ходом первый переворачивает карту №9 или №15, то указанный ответный ход второго (приводящий к игре на двух рядах по 6 карт) позволяет второму победить симметричной игрой. Остановимся подробнее на случае, когда следующим ходом переворачивается карта №1, №6, №8 или №16 (что приводит к игре на двух рядах - из 5 и из 8 карт):

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
	4	4	2	4	4			11	11	9	5	5	15	14	14

Если следующим ходом первый переворачивает карту №2. №3, №4. №5 или №6, всё сводится к рассмотренному нами случаю игры на двух рядах из 2 и 8 карт (случай был рассмотрен при х=12). Ходы №9, №10, №11. №14, №15, №16 приводят к победе второго при помощи симметричной игры, ходы №12 и №13 первого игрока также приводят к игре на двух рядах по три карты (симметричная игра) и одном ряду из четырёх карт (рассмотренный случай).

При х=19 своим первым ходом второй переворачивают карту №8:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
9	10	10	12	10	10	9		7	6	10	4	6	6	4	17	6	7

Если своим следующим ходом первый игрок переворачивает карту №2, №6, №10 или №17 приводят к уже рассмотренному случаю игры на рядах из 5 и 8 карт. Если следующим ходом будет перевёрнута карта №3 или №5 игра продолжается на ряде из четырёх карт (выигрывает второй) и на двух рядах из 2 и 8 карт (выигрывает второй), если карта №4, №12 или №15 - на двух рядах по три карты (симметрия) и на двух рядах из трех и шести карт (выигрывает второй), если карта №13 или №14 - на двух рядах по 5 карт (симметрия) и на ряду из 4 карт (выигрывает второй), карта №11 или №16 - на двух рядах из 6 карт (симметрия). Случай, когда первый переворачивает какую-либо другую карту, приводит к игре на рядах из 6 и 9 карт. Рассмотрим этот случай.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
	10	14	12	16	14	18			2	12	4	14	3	14	5	16	7

Все случаи приводят к уже рассмотренным позициям, кроме хода, при котором первый переворачивает карту №13 или №15. Если будет сделан именно такой ход, то игра продолжается на ряду из 4 карт (выигрывает второй) и на двух рядах из 3 и 6 карт (выигрывает второй).

При х=21 выигрывает первый:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
11	10	4	3	13	13	13	16	13	20	1	8	9	8	8	8	18	17	10	10

Если своим первым ходом второй перевернёт карту №1, №10, №11 или №20, игра продолжится на двух рядах из 9 карт - симметрия. Ходы, которыми второй переворачивает карту №2 или №19, приводят к уже рассмотренному случаю игры на рядах из 7 и 10 карт. В ответ на ходы №6, №7, №8, №14, №15, №16 первый сводит игру к игре на трёх рядах из 5, 6 и 7 карт. Рассмотрим этот случай:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
14	17	14	17	14		17	19	14	14	15	17		1	11	11	2	11	8	1

Ходы №2, №4 и №17 приводят к уже рассмотренному случаю (три ряда по 3 карты и один - из 6 карт). Ходы №1, №5, №14 и №20 позволяют первому играть за второго на ряду из 4 карт (выигрывает второй) и на двух рядах из 6 карт (симметрия). Ход №3 позволяет первому выиграть при помощи симметрии (игра продолжается на двух рядах из двух карт и на двух - из шести) как и ходы №7 и №12. Ходы №8, №11, №15 и №19 приводят к уже рассмотренному случаю. Ходы №9, №10 позволяют первому играть за второго на двух рядах из 2 и 5 карт и на двух рядах из 3 и 6 карт. Ходы №16 и №18 приводят к игре на двух рядах по 4 карты (симметрия) и на двух рядах из 2 и 5 карт (первый играет за второго и выигрывает).

Во всех шести остальных случаях получаем одну из двух следующих позиций:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
11	11			8	13	14	5	13	14	1	19	6	1	11	12	20	11	12	17

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
11	17	14	17	17	14	17	11		17	8	17		6	6	17	10	17	6	6

Укажем стратегию первого на обеих. После хода №3 или №4:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
11	11			8	13	14	5	13	14	1	19	6	10	11	12	20	11	12	17

Ходы №1, №2, №7, №10, №11, №14, №15, №18, приводят или к уже рассмотренным нами случаям, или к возможности симметричной игры, словом, к очевидному результату. Ходы №5, №8, №17 и №20 приводят к игре на двух рядах по две карты (симметрия) и на одном ряду из 12 карт (первый играет за второго и выигрывает). Рассмотрим результаты ходов №9 или №16:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
14	14								17	15	17		1	11	11	10	11	11	1

Ряд из четырёх карт (с 5-ой по 8-ую) можно не учитывать - на ней выигрывает второй, следовательно, тот, кто выигрывает на остальной части, сыграет на этой части за второго и она на результате игры никак не скажется. Ходы №1, №2, №11, №14, №15, №16, №18, №19 и №20 приводят к уже рассмотренным случаям. Ходы №10, №12 и №17 приводят к позиции, при которой первый может выиграть за второго по симметрии.

Рассмотрим результаты ходов №6, №12, №13, №19 (все они приводят к одной и той же позиции):

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
14	14					17	15	14	14	19	17		1	8	8	7	8	11	1

Все ходы приводят к уже рассмотренным ранее позициям.

После ходов №9 или №13:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
11	17	14	17	17	14	17	11		17	8	17		6	11	17	4	17	11	6

Ходы №1, №2, №3, №6, №7, №8, №11, №14, №15, №19 и №20 приводят к уже рассмотренным нами позициям. Ходы №4, №5 и №17 приводят к игре на четырёх рядах по три карты (симметрия) и одном ряду из четырёх карт (первый играет за второго и выигрывает). Ходы №10, №12, №16 и №18 приводят к позиции, когда игра продолжается на двух рядах по три карты (симметрия) и на двух рядах из 2 и 8 карт (случай, рассмотренный выше).

Таким образом, все случаи для х=21 рассмотрены.

При х=23 второй переворачивает вторую карту и играет за второго на 20 картах по только что приведённому алгоритму.

При х=25 второй своим первым ходом переворачивает карту №11 и выигрывает:

1	2	3	4	5	6	7	8	9	10
14	16	17	18	16	16	18	19	20	14

12	13	14	15	16	17	18	19	20	21	22	23	24
14	14	12	4	2	3	4	8	9	7	23	22	22

Ходы №4, №7 и №18 приводят к позиции, когда игра продолжается на трёх рядах по 6 карт и одном ряду из 3 карт. На двух рядах из 6 карт второй применяет симметрию, случай игры на двух рядах из 3 и 6 карт рассмотрен выше. Ходы №2, №9, №16 и №20 приводят к игре на одном ряду из 4 карт (выигрывает второй) и на двух рядах по 8 карт (симметрия). Ходы №15 и №21 приводят к игре на двух рядах по три карты (симметрия) и на двух рядах из 6 и 9 карт (случай рассмотрен выше). Ходы №12, №13, №14, №22, №23 и №24 приводят к игре на двух рядах по 10 карт (симметрия). Ходы №3, №8, №17 и №19 приводят к игре на двух рядах из 7 карт (симметрия). Ходы №5 и №6 приводят к игре на двух рядах по 4 карты (симметрия) и на двух рядах из 5 и 8 карт (случай рассмотрен выше). Ходы №1 и №10 приводят к следующей позиции:

1	2	3	4	5	6	7	8	9
18	17	15	15	16	15	24	22	21

12	13	14	15	16	17	18	19	20	21	22	23	24
15	15		12	5	2	1	5	5	9	8	5	12

Ходы №12, №13, №15 и №24 приводят к игре на двух рядах по 9 карт (симметрия). Ходы №5, №16 и №23 приводят к игре на двух рядах по 4 карты (симметрия) и на двух рядах из 2 и 8 карт (случай рассмотрен выше). Ходы №3 и №7 приводят к игре на двух рядах по 2 карты (симметрия) и на двух рядах из 6 и 9 карт (случай рассмотрен выше). Ходы №2, №8, №17 и №22 приводят к игре на двух рядах по 2 карты (симметрия). Ходы №1, №9, №18 и №21 приводят к игре на двух рядах их 3 и6 карт (рассмотренный случай) и на двух - из 2 и 8 карт (рассмотренный случай). Ходы №19 и №20 приводят к игре на трёх рядах из 4 карт (рассмотренный случай и на двух рядах из 2 и 5 карт(рассмотренный случай). Ходы №4 и 6 приводят к игре на двух рядах из 2 и 5 карт (рассмотренный случай) и на двух - из 3 и 9 карт. Докажем, что при игре на 3 и 9 картах второй тоже выигрывает.

1	2	3		16	17	18	19	20	21	22	23	24
17	20	17		18	1	16	22	2	18	24	1	22

Все случаи приводят к ранее рассмотренным вариантам.

При х=27 своим первым ходом второй переворачивает карту №12 и выигрывает:

1	2	3	4	5	6	7	8	9	10	11
13	17	14	19	17	25	22	20	25	22	26

13	14	15	16	17	18	19	20	21	22	23	24	25	26
1	6	13	20	2	3	4	8	9	10	19	25	6	11

Ходы №1, №11, №13 и №26 приводят к уже рассмотренным случаям. Ходы №2, №10, №17 и №22 приводят к игре на ряду из 4 карт (рассмотренный случай) и на 2 рядах из 9 карт (симметрия). Ходы №6, №14 и№25 приводят к игре на двух рядах по 5 карт (симметрия) и на одном ряду из 12 карт (рассмотренный случай). Ходы №3 и №9 приводят к игре на ряду из 12 карт (рассмотрено) и двух рядах из 2 и 8 карт (рассмотрено). Ходы №4, №8, №19 и №20 приводят к игре на двух рядах из 7 карт (симметрия) и двух рядах из 3 и 6 карт (рассмотрено). Ходы №5 и №7 приводят к игре на двух рядах из 4 карт (симметрия) и на двух рядах 6 и 9 карт (рассмотрено). Ходы №15 и №24 приводят к игре на двух рядах из 11 карт (симметрия). Ходы №18 и №20 приводят к игре на двух рядах из 2 и 5 карт (рассмотрено) и на двух рядах из 8 карт (симметрия). Ход №16 и ход №23 приводят к игре на четырёх рядах: на 2 рядах из 3 карт (симметрия) и на двух рядах из 7 и 10 карт. Докажем, что на рядах из 7 и 10 карт второй выигрывает:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
9	10	13	12	14	10	9		11	11	10	4	3	5	4	18	16	16

Все случаи приводят к уже рассмотренным нами позициям.

На этом наш перебор закончен.

Есть гипотеза, что при х = 8у + 1 и х = 8у + 3 второй выигрывает, переворачивая карту № 4у-1 и № 4у соответственно. Заметим, что во всех подобных случаях, рассмотренных выше, выигрывал именно этот ход.

§4. Заключение

В результате нашего исследования полностью изучена игра (n,k) для одного игрока: получены условия простоты игры (теорема 1), полностью рассмотрены правильные игры (теорема 2), и, в частности, количества правильных игр (п. 2.2). Построены классы эквивалентности игр (теоремы 3 и 4).

Дополнительно рассмотрена задача о соответствующем преобразовании конечных двоичных последовательностей (теоремы 5-7).

Получены существенные результаты для игры с двумя игроками (четное количество компонент и четное количество карт в компонентах, а также случаи нечетного числа карт вплоть до 27 карт). Предложена гипотеза для общего случая.

Направления дальнейшего исследования:

1. Закончить исследование игры для двух игроков, в частности, доказать (или опровергнуть) гипотезы § 3.

2. Исследовать игру для двух игроков, когда карты расположены не по окружности, а в форме восьмёрки, прямоугольника MЧN и т.п.

3. Исследовать возможность перемены длины хода.

Пусть во время игры разрешается один раз поменять длину хода. Будем называть игру длины n игрой (n,k,l), если изначальную длину хода k в некоторый момент можно заменить на l.

Теорема 8. Правильная игра (n,k,l) оставляет неперевёрнутыми d(n,k,l) карт.

Чтобы неперевёрнутыми остались ровно d(n,k,l) карт, в каждой из n/d(n,k) компонент перевернём все карты кроме одной таким образом, чтобы все карты, оставшиеся неперевёрнутыми, представляли собой d(n,k,l) компонент вида (d(n,k)/d(n,k,l),l).