Математические игры и стратегии.

Математические игры и выигрышные стратегии. Игры с симметричной стратегией. Выигрышные позиции. Игры на шахматной доске.

Конспект занятия "Математические игры и стратегии."


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задачи:

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

Решить ту же задачу в общем виде, про шоколадку MxN.

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

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

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

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

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

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

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

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

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



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



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

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

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

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



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

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

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

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




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


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

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

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

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

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


Дополнительно:


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

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

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

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

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

числа;

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

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






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

Задание 1

(2 балла)

Играют двое. Начинающий называет одно из чисел: 1, 2, 3, 4. Второй игрок прибавляет к этому числу одно из этих же чисел: 1, 2, 3, 4 и называет вслух получившуюся сумму. То же самое делает затем первый игрок и т.д. Победителем считается тот, кто первым назовёт число 40. У которого игрока есть выигрышная стратегия? (в ответ запишите 1 или 2 – номер игрока).

Задание 2

(2 балла)

Двое игроков делят 2 кучки конфет, 9 и 11, на более мелкие кучки. За 1 ход можно разделить 1 кучку на 2 меньших. Проигрывает тот, кто не сможет сделать ход. Сколько ходов в игре?

Задание 3

(3 балла)

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

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