Игры и стратегии

В этом занятии мы рассмотрим класс задач, часто встречаемый во многих математических турнирах. В задачах на игры обычно играют двое, и нужно ответить, кто выиграет при правильной игре - игре, в которой оба соперника равны по силам. Чтобы решить такую задачу нужно ответить - кто выиграет и как он должен играть, чтобы выиграть.

Конспект занятия "Игры и стратегии"

Игры и стратегии.

Игры и стратегии – отдельный класс математических задач. Чаще всего играют двое. При этом в условии оговорены правила игры. Нужно показать, какой из игроков имеет возможность выиграть независимо от ходов соперника.

В решении игровой задачи нужно записать:

I) ход первого игрока;

II) алгоритм ходов в ответ на каждый ход соперника, т. е. стратегию победы;

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

Основные (но не единственные) идеи стратегий:

  • Игры-шутки.

  • Игры, использующие симметрию.

  • Игры, в которых стратегия — дополнение до фиксированного числа.

  • Игры, использующие метод выигрышных позиций

Сегодня на занятии мы подробно разберем каждую идею.

1. Игры-шутки.

Игры – шутки – это такие игры, где для построения выигрышного алгоритма можно ничего и не знать, так как в них результат будет зависеть не от игры партнеров, а от начальных условий. Однако для этого в решении нужно заметить, что это игра-шутка, а не какая-то другая, в которой нужно искать выигрышную стратегию. На самом деле, нет никакой стратегии (а нас хотят обмануть, что она якобы есть!) Просто... как бы кто ни ходил, либо всегда выиграет первый игрок (тот, кто начинает игру), либо всегда второй. Задача - в том, чтобы математически доказать такую закономерность. Для доказательства обычно находится какая-то величина, которая понятно чему равна в начале и конце и понятно как изменяется на каждом ходу - тут даже частенько число ходов до конца однозначно посчитать можно. Это величина называется инвариантом (четность – самый известный инвариант в математике).

Инвариант (от лат. invarians - неизменяющийся), в математике - величина, остающаяся неизменяемой при тех или иных преобразованиях.

1. В ряде задач встречается следующая ситуация. Некоторая система последовательно изменяет своё состояние, и требуется выяснить нечто о её конечном состоянии. Полностью проследить за всеми переходами может оказаться делом сложным, но иногда ответить на требуемый вопрос помогает вычисление некоторой величины, характеризующей состояние системы и сохраняющейся при всех переходах (такую величину называют инвариантом для рассматриваемой системы). Ясно, что тогда в конечном состоянии значение инварианта будет то же самое, что и в начальном, т.е. система не может оказаться в состоянии с другим значением инварианта.

2. На практике этот метод сводится к тому, что некоторая величина вычисляется двумя способами: сначала она просто вычисляется в начальном и конечном состояниях, а затем прослеживается её изменение при последовательных мелких переходах.

3. Наиболее простым и часто встречающимся инвариантом является четность числа; инвариантом может быть также и остаток от деления не только на 2, но и на какое-нибудь другое число. Для построения инвариантов иногда бывают полезны вспомогательные раскраски, т.е. разбиения рассматриваемых объектов на несколько групп (каждая группа состоит из объектов одного цвета).

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

Отметим, что часто для нахождения идеи решения задачи можно использовать «метод маленьких чисел», т. е. начинать поиск решения с небольших чисел.

Задачи:

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

  2. Имеется три кучки камней: в первой - 10, во второй - 15, в третьей - 20. За ход можно разбить любую кучку на две меньшие. Проигрывает тот, кто не может сделать ход. Кто выиграет?

  3. На доске написаны цифры: 10 нулей и 10 единиц. За ход можно стереть две любые цифры и написать вместо них 0, если они были одинаковые или 1, если они были разные. Если на доске остается 1 - выигрывает первый. Если 0 - второй.

  4. На доске записаны 2015 единицы и 2016 нулей. Каждый из двух игроков выбирает два произвольных числа, стирает, и записывает на их место 0, если они были равны, и 1, если нет. В конце на доске остается только одно число. Если это число 1, то выигрывает первый игрок, если 0, то второй. Кто выиграет?

2. Симметрия.

Очень простой, но мощный и красивый метод решения игровых задач - симметричная стратегия. Суть его - делать каждый раз ход, симметричный ходу противника или дополняющий его до чего-либо. Доказательство правильности нашей стратегии будет пользоваться тем, что после каждого нашего хода позиция симметрична: раз так, то если противник сумел сделать свой ход, то и мы сможем сделать ход, симметричный ему.

Задачи к теме:

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

  2. Двое играют, поочередно выставляя крестики и нолики на квадратном поле 9х9. В конце каждый получает очко за каждую строку и столбец, в которых его знаков больше. Сможет ли первый игрок выиграть?

  3. Имеется две кучки камней — по 7 в каждой. За ход можно взять любое количество камней, но только из одной кучки. Проигрывает тот, кто не может сделать ход. Кто выиграет?



3. Игры, в которых стратегия — дополнение до фиксированного числа.



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

Рассмотрим пример такой стратегии на конкретных задачах.

  1. Двое играют в игру. Ходы, которые делаются по очереди, заключаются в том, что из кучки в 26 камней убирается любое число камней от 1 до 5. Выигрывает тот, кто возьмет последний камень. Кто выиграет в данной игре?

  2. Двое играют в игру, которая заключается в прибавлении к нулю любого натурального числа, не превышающего семи. Выигрывает тот, кто скажет число 50. Кто выиграет в данной игре?

5. Метод выигрышных позиций

Этот метод основан на рассмотрении каждой позиции с точки зрения пользы для игрока, которому предстоит ход. Начинаем рассматривать с конца – с последнего хода, затем предпоследний и т.д.

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

  2. "Хромая ладья" может ходить по прямой вправо или вверх. Исходно она стоит в нижнем левом углу шахматной доски. Играют двое. Выигрывает тот, кто поставит ладью в верхний правый угол.

  3. Имеются две кучки конфет: в одной — 20, в другой — 21. За ход нужно съесть все конфеты в одной из кучек, а вторую разделить на две необязательно равные кучки. Проигрывает тот, кто не может сделать ход. Кто выиграет?




Игры и стратегии. Задачи.


  1. На концах клетчатой полоски 1 х 20 стоит по шашке. За ход разрешается сдвинуть любую шашку в направлении другой на одну или две клетки. Перепрыгивать через шашку нельзя. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?

  2. На столе лежит 25 спичек. Двое по очереди берут от 1 до 3 спичек. Проигрывает тот, кому спичек не осталось. Кто выигрывает при правильной игре? А если спичек 24?

  3. На столе лежат 2 кучи спичек в одной 7, в другой 10. За один ход разрешается взять 1 спичку из одной (любой) кучки или по спичке из двух кучек сразу. Кто не может сделать ход (спичек не осталось) – проигрывает. Кто выиграет при правильной игре?

Попробуйте рассмотреть эту задачу на шахматной доске.

  1. В куче 25 камней. Два игрока берут по очереди или 2, или 4, или 7 камней. Проигрывает тот, у кого нет хода. Кто победит при правильной игре?

  2. На доске записаны два числа: 2015 и 2016. Петя и Вася ходят по очереди, начинает Петя. За один ход можно

— либо уменьшить одно из чисел на его ненулевую цифру или на ненулевую цифру другого числа;

— либо разделить одно из чисел пополам, если оно чётное.

Выигрывает тот, кто первым напишет однозначное число. Кто из них может выиграть, как бы ни играл соперник?


  1. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или пять камней или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 20 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда в куче становится не менее 41. Победителем считается игрок, сделавший последний ход, то есть первым получившим кучу, в которой будет 41 или больше камней. В начальный момент в куче было S камней ; 1 S 40.

Задание 1.

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

б ) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.



  1. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или пять камней или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 20 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда в куче становится не менее 41. Победителем считается игрок, сделавший последний ход, то есть первым получившим кучу, в которой будет 41 или больше камней. В начальный момент в куче было S камней ; 1

Задание 2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причем одновременно выполняются два условия: Петя не может выиграть за один ход; Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети. 

  1. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или пять камней или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 20 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда в куче становится не менее 41. Победителем считается игрок, сделавший последний ход, то есть первым получившим кучу, в которой будет 41 или больше камней. В начальный момент в куче было S камней ; 1

Задание 3. Укажите значение S, при котором одновременно выполняются два условия : У Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети ; У Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы ). На ребрах дерева указывайте, кто делает ход, в узлах – количество камней в позиции. 


Задания по теме для самостоятельного решения

Задание 1

(2 балла)

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

Варианты ответов:

А) первый, в игре 27 ходов

Б) второй, в игре 28 ходов,

в) первый, в игре 28 ходов

г) второй, в игре 27 ходов,

Задание 2

(2 балла)

Имеется две кучки камней — по 5 и 8 в каждой. За ход можно взять любое количество камней, но только из одной кучки. Проигрывает тот, кто не может сделать ход. Кто выиграет?

А) первый, используем дополнение до числа.

Б) второй, используем симметрию,

в) первый, используем симметрию,

г) второй, используем метод выигрышных позиций.

Задание 3

(2 балла)

На столе лежит 25 спичек. Двое по очереди берут от 1 до 4 спичек. Проигрывает тот, кому спичек не осталось. Кто выигрывает при правильной игре? А если спичек 24?

 А) первый, используем дополнение до числа 6.

Б) второй, используем дополнение до числа 6,

в) первый, используем дополнение до 5

г) второй, используем дополнение до 4

д) второй, используем дополнение до 5.

Проверить правильность выполнения заданий вы можете в автоматическом режиме в разделе домашние задания на странице с курсом "Математика Школьный курс + олимпиады 2016"