Два игрока, Коля и Саша, играют в следующую игру. На столе в кучке лежат фишки. На лицевой стороне каждой фишки написано двузначное натуральное число, обе цифры которого находятся в диапазоне от 1 до 4. Никакие две фишки не повторяются. Игра состоит в том, что игроки поочерёдно берут из кучки по одной фишке и выкладывают в цепочку на стол лицевой стороной вверх таким образом, что каждая новая фишка ставится правее предыдущей и ближайшие цифры соседних фишек совпадают. Верхняя часть всех выложенных фишек направлена в одну сторону, то есть переворачивать фишки нельзя. Например, из фишки, на которой написано 12, нельзя сделать фишку, на которой написано 21.
Первый ход делает Коля, выкладывая на стол любую фишку из кучки. Игра заканчивается, когда в кучке нет ни одной фишки, которую можно добавить в цепочку. Тот, кто добавил в цепочку последнюю фишку, выигрывает, а его противник проигрывает.
Будем называть партией любую допустимую правилами последовательность ходов игроков, приводящую к завершению игры. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Описать стратегию игрока—значит указать, какую фишку он должен выставить в любой ситуации, которая ему может встретиться при различной игре противника.
Пример партии.
Пусть на столе в кучке лежат фишки: 11, 12, 13, 21, 22, 23.
Пусть первый ход Коли 21.
Саша может поставить 12, 11 или 13. Предположим, он ставит 12.Получим цепочку 21-12.
Коля может поставить 22 или 23. Предположим, он ставит 22. Получим цепочку 21-12-22.
Саша может поставить только фишку со значением 23. Получим цепочку 21-12-22-23.
Перед Колей в кучке остались только фишки 11 и 13, то есть нет фишек, которые он мог бы добавить в цепочку. Таким образом, партия закончена, Саша выиграл.
Выполните следующие три задания при исходном наборе фишек в кучке {11, 12, 13, 21, 23, 31, 32, 33}.
Задание 1. Приведите пример самой короткой партии, возможной при данном наборе фишек. Если таких партий несколько, достаточно привести одну.
Задание 2. Пусть Коля первым ходом пошёл 11. У кого из игроков есть выигрышная стратегия, позволяющая в этой ситуации выиграть своим четвёртым ходом? Постройте в виде рисунка или таблицы дерево всех партий, возможных при реализации выигрывающим игроком этой стратегии. На рёбрах дерева указывайте ход, в узлах — цепочку фишек, получившуюся после этого хода.
Задание 3. Укажите хотя бы один способ убрать 2 фишки из исходного набора так, чтобы всегда выигрывал не тот игрок, который имеет выигрышную стратегию в задании 2. Приведите пример партии для набора из 6 оставшихся фишек.
Задание 1. Пример кратчайшей партии: 21-12-23-32.
Возможен другой вариант ответа: 23-32-21-12.
Пояснение: партия будет кратчайшей, если первый игрок начнёт игру с фишки, первая цифра которой встречается реже первых цифр остальных фишек, и, если это возможно, партия не содержит «дублей» — фишек вида «xx». Ответный ход противника, в случае кратчайшей партии, должен быть «симметричным», если это возможно. То есть на ход фишкой «xy» ответным ходом должен быть «yx», если это возможно.
Задание 2. Стратегия, позволяющая выиграть своим четвёртым ходом, есть у Коли.
Ниже представлена таблица выигрышных стратегий Коли. В таблице показаны все ходы Саши и только выигрышные ходы Коли. Заключительные позиции (в них выигрывает Коля) подчёркнуты.
| Коля 1-й ход |
11 11 |
||
| Саша 1-й ход |
12 11-12 |
13 11-13 |
|
| Коля 2-й ход |
21 11-12-21 |
32 11-13-32 |
|
| Саша 2-й ход |
13 11-12-21-13 |
23 11-13-32-23 |
21 11-13-32-21 |
| Коля 3-й ход |
32 11-12-21-13-32 |
31 11-13-32-23-31 |
12 11-13-32-21-12 |
| Саша 3-й ход |
23 11-12-21-13-32- 23 |
12 11-13-32-23-31- 12 |
23 11-13-32-21-12- 23 |
| Коля 4-й ход |
31 11-12-21-13-32- 23-31 |
21 11-13-32-23-31- 12-21 |
31 11-13-32-21-12- 23-31 |
Пояснение. Стратегия Коли заключается в том, что он должен ставить фишки, которые не заканчиваются на 3, тем самым не давая возможность Саше сделать ход «33». Например, если после ходов 11-13-31-12 Коля поставит фишку 23, то выиграет Саша: 11-13-31-12-23-33-32-21.
Задание 3.Можно убрать фишки 11 и 33. В этом случае независимо от ходов обоих игроков Саша выиграет (или своим вторым, или своим третьим ходом).
Пример такой партии:
| Игрок | Коля | Саша | Коля | Саша | Коля | Саша |
| Ход | 23 | 31 | 13 | 32 | 21 | 12 |
Пояснение. После того, как из исходного набора будут убраны фишки «11», «33», останется чётное количество фишек, при этом для каждой фишки есть «симметричная» ей, поэтому второй игрок всегда выигрывает.