Занятие 3. Игры. Симметрия. Разбиение на пары.

Правильная игра. Будем говорить, что у игрока есть выигрышная стратегия, если он может играть так, чтобы выиграть вне зависимости от ходов своего противника. Будем считать, что игроки достаточно умны для того, чтобы в случае существования у них выигрышной стратегии пользоваться ей, а не давать выиграть другому. Правильной игрой мы будем называть именно такую игру, в которой нет “глупых” ходов. А вопрос: “Кто выигрывает при правильной игре?” нужно понимать как: “У какого из игроков есть выигрышная стратегия?”

Пример:

В двух кучках лежат предметы, по 2013 предметов в каждой. За ход разрешается взять произвольное количество предметов, но только из одной кучки. Проигрывает тот, кто не может сделать очередной ход. Найдите выигрышную стратегию для второго игрока. А если 3 кучки?

Задачи:

1. На столе выложены две одинаковых монеты. Играют двое. Каждый игрок за один ход может взять любую из монет и разменять ее меньшими монетами, но на ту же сумму. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре? (Монеты берутся из набора 2, 3, 5, 10, 15, 20, 50 копеек и 1 рубль).

2. Два миллионера по очереди кладут пятаки на круглый стол, так, чтобы они не накладывались друг на друга. Проигрывает тот, кто не может сделать хода. Как надо играть миллионеру, который кладёт первый пятак, чтобы наверняка выиграть?

3. а) Анечка и Славик ломают шоколадку размером 6 17. За один ход разрешается сделать прямолинейный разлом по любому из имеющихся углублений. Проигрывает тот, кто первым отломит дольку 1´1. Начинает Анечка, кто выиграет при правильной игре? б) А если выигрывает тот, кто первым отломит 1х1?

4. У ромашки а) 12 лепестков; б) 11 лепестков. За ход разрешается оторвать либо один лепесток, либо два рядом растущих лепестка. Проигрывает тот, кто не может сделать хода. Кто выигрывает при правильной игре?

5. На доске в строку написаны целые числа от 1 до 2013. Игроки по очереди расставляют между ними знаки "+" или "–". После того, как все места заполнены, подсчитывается результат. Если он четен, выигрывает первый игрок, если нечетен – второй игрок. Кто выигрывает при правильной игре?

6. В каждой клетке доски а) 11 × 11 б) 12 × 12 стоит шашка. За ход разрешается снять с доски любое количество подряд идущих шашек либо из одного вертикального, либо из одного горизонтального ряда. Выигрывает снявший последнюю шашку. Кто выигрывает при правильной игре?

Дополнительные задачи:

7. Дана доска в виде трех пересекающихся шестиугольников, разбитая на треугольники (рис.1). Двое играют в следующую игру: первый своим первым ходом ставит короля на любую клетку, после чего, начиная со второго, они поочередно двигают его по доске (в соседнюю по стороне клетку), причем запрещается ходить в ранее посещенные клетки. Проигрывает тот, кто не может сделать хода. Кто выигрывает при правильной игре и как он должен играть?

8. Двое играют в следующую игру: первый выбирает любое поле на доске 8 × 8, ставит туда короля и делает ход (король может ходить в соседние и соседние по диагонали клетки), при условии, что на эту клетку раньше никто не вставал. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре