Статья на тему Стратегические игры

СТРАТЕГИЧЕСКИЕ ИГРЫ
Жук В.В., к.ф.-м.н.,
учитель математики РСФМСШИ им. О. Жаутыковаvladimir_zhuk @mail.ruВ задачах на стратегию требуется определить, кто и как выиграет в заданной игре, если оба игрока будут наилучшим образом отвечать на ход соперника, придерживаясь оптимальной для себя стратегии. Такие действия каждого из соперников называются правильной игрой. Таким образом, при правильной игре проигрыш одного из игроков обусловлен не его ошибками или волей случая, а выигрыш невозможен, если полагаться на удачу. Во всех задачах, которые буду рассмотрены в данной статье вопрос один: кто из соперников выиграет при правильной игре? Поэтому этот вопрос в условиях задач специально оговариваться не будет. При ответе на этот вопрос мы должны определить кто из игроков, действуя наилучшим образом, выиграет в этой игре, какие бы действия при этом не предпринимал другой игрок, также необходимо привести выигрышную стратегию.
Основные идеи, которые используются при решении задач на стратегию:
Соответствие: наличие удачного ответного хода (симметрия, разбиение на пары,…) Анализ с конца: последовательно определяются позиции, выигрышные и проигрышные для начинающего
Переход хода: если есть возможность воспользоваться стратегией соперника, то наши дела не хуже, чем у него
Рассмотрим на примерах некоторые подходы к решению задач на стратегию.

КОГДА СТРАТЕГИЯ НЕ ИМЕЕТ ЗНАЧЕНИЯ
2653665555625В некоторых играх стратегия не важна, поскольку выигрыш или проигрыш вообще не зависит от действий игроков, а предопределен самими правилами игры. В этом разделе рассмотрим задачи, в которых возникает подобная ситуация.
Задача №1 (ТГ 86). Двое играют в следующую игру. Имеется три кучки камней в первой – 10, во второй – 15, в третьей – 20. За ход разрешается разбить любую кучку на две меньшие. Проигрывает тот, кто не сможет сделать ход.
635021590Решение. Заметим, что после каждого хода (независимо от выбранной стратегии игроков) количество кучек увеличивается на 1. Изначально количество кучек равно 3. Игра закончится, когда в каждой кучке окажется ровно по одному камню (только в этом случае невозможно сделать ход). Количество кучек в конце игры равно общему количеству камне, то есть . Значит, всего будет сделано хода. Последним сможет сделать ход второй игрок, и он в этой игре выигрывает независимо от того, какой стратегии будут придерживаться игроки.
Ответ: выигрывает второй игрок, стратегия значения не имеет.
407860590170Задача №2 (ТГ 86). Двое по очереди ломают шоколадку 6×8. За ход разрешается сделать прямолинейный разлом любого из кусков вдоль их углубления. Проигрывает тот, кто не сможет сделать ход.
Решение. После каждого разлома количество кусков увеличивается на 1. Изначально был один кусок (целая шоколадка), в конце игры количество кусков будет равно . За всю игру будет сделано 47 разломов. Потому в этой игре, как бы ни играли соперники, победу всегда будет одерживать первый игрок.
Ответ: какой бы стратегии ни придерживались соперники, выигрывает первый игрок.
Впрочем, горечь поражения в этой игре компенсируется дальнейшим поеданием участниками игры 48 кусочков шоколада, если только победитель не забирает всё…
-12065062230Задача №3. В одном ящике лежат 15 синих шаров, в другом – 12 белых. Одним ходом каждому разрешается взять три синих шара или два белых. Выигрывает тот, кто берёт последние шары.
Решение. Разобьем шары, лежащие в ящике на «блоки», состоящие из трёх синих или из двух белых шаров. Всего получим 5 синих и 6 белых «блоков», в общей сложности – 11 «блоков». За один ход количество «блоков» уменьшается на 1. Следовательно, в течение игру будет сделано 11 ходов. Значит, независимо от стратегии игроков выигрыш всегда будет оставаться за первым игроком.
Ответ: выигрывает первый игрок, стратегия значения не имеет.
Задачи для самостоятельного решения
На доске написаны 10 единиц и 10 двоек. За ход можно стереть две любые цифры и, если они были одинаковами, написать 2, а если разными – 1. Если последняя оставшаяся на доске цифра – 1, то выиграл первый игрок, если 2 – то второй.
Двое выписывают шестизначное число, выставляя по очереди по одной цифре, начиная со старшего разряда. Если получившееся число разделится на 7, то выигрывает сделавший последний ход, иначе – начинающий.
Дана клетчатая доска размерами: а) 9×10; б) 10×12; в) 9×11. За ход разрешается вычеркнуть любую горизонталь или любую вертикаль, если в ней к моменту хода есть хотя бы одна невычеркнутая клетка. Проигрывает тот, кто не может сделать ход.
349250-254000
25247603810
СИММЕТРИЧНАЯ СТРАТЕГИЯ
В следующих задачах выигрышная стратегия обладает некоторым свойством симметрии, при которой только что сделанный противником ход не препятствует осуществлению стратегии.
-7683536195Задача №4. Двое по очереди ставят слонов в клетки шахматной доски так, чтобы слоны не били друг друга. (Цвет слонов значения не имеет). Проигрывает тот, кто не сможет сделать ход.
Решение. Второму игроку для выигрыша следует придерживаться следующей стратегии: разделить шахматную доску горизонтальной прямой на две равные части и каждый раз ставить своего слона на поле, симметричное относительно этой прямой полю, на которое первый игрок последним ходом поставил своего слона.
224663024130
Ответ: второй игрок выигрывает при правильной игре, придерживаясь указанной в решении стратегии.
635062865Рассмотрите другие шахматные фигуры, изменится ли тогда ответ в задаче?
3849370165100339534592710
Задача №5. Дана клетчатая доска 10×10. За ход разрешается покрыть любые две соседние клетки доминошкой (прямоугольником 1×2) так, чтобы доминошки не перекрывались. Проигрывает тот, кто не может сделать ход.
Решение. Второму игроку следует свою доминошку ставить симметрично относительно центра доски доминошке соперника. При такой стратегии на каждый ход первого игрока найдется место, куда может походить второй. Поэтому у второго игрока идут не хуже, чем у первого. Поэтому, в конце концов, второй игрок выиграет, если будет придерживаться данной стратегии.
Ответ: при правильной игре выиграет второй игрок.
-3175013335Задача №6. В каждой клетке доски 11×11 стоит шашка. За ход разрешается снять с доски любое число подряд идущих шашек либо из одного вертикального, либо из одного горизонтального ряда. Выигрывает снявший последнюю шашку.
Решение. Первый игрок начальным своим ходом снимает шашку, стоящую в центральной клетке. Затем действует симметрично ходам второго игрока. Этой стратегия является выигрышной для первого игрока, поскольку он может сделать ответный ход на любой ход соперника.
Ответ: при правильной игре первый игрок выигрывает.
Задача №7 (МО 68). На окружности расставлены 20 точек. За ход разрешается соединить любые две из них отрезком, не пересекающим отрезков, проведённых ранее. Проигрывает тот, кто не сможет сделать ход.

Решение. Пронумеруем расставленные на окружности точки числами 1, 2, …, 20, как показано на рисунке выше. Первый игрок своим начальным ходом соединяет отрезком точки с номерами 1 и 11. Разобьём точки из разных частей окружности на пары 2–20, 3–19, …, 10–12 (заметим, что сумма чисел в каждой паре равна 22). Дальнейшая стратегия первого игрока такова. На любой ход соперника, соединившего точки с номерами и , он отвечает симметричным ходом, соединяя точки с парными номерами и .
Ответ: первый игрок выигрывает при правильной игре, стратегия указана в решении.
257746577470
Задача №8 (ТГ 86). Двое по очереди ломают шоколадку 10×5. За ход разрешается сделать прямолинейный разлом любого из кусков вдоль их углубления. Выигрывает тот, кто первым сможет отломить дольку 1×1.
Решение. Сначала первый игрок делит шоколадку на два равных куска размером 5×5. Вторым ходом второй игрок не сможет отломить дольку размером 1×1. Дальнейшие действия первого игрока зависят от ситуации. Если у него появилась возможность отломить дольку размером 1×1, то он это делает и выигрывает. В противном случае от поступает симметрично действиям соперника (в силу симметрии, если у первого игрока не появилась возможности отломить дольку размером 1×1, то такой возможности не было и у второго игрока).
Ответ: при правильной игре выигрывает первый игрок.
Задачи для самостоятельного решения
Имеется две кучи камней по 11 в каждой. За ход разрешается взять любое количество камней, но только из одной кучи. Проигрывает тот, кому нечего брать.
Имеются три кучи камней. Число камней во всех кучах одинаково. Двое играющих берут по очереди любое число камней из любой кучи, но только из одной. Выигрывает тот, кто берёт последние камни.
Имеется 10 фишек: 2 белых, 2 чёрных, 2 красных, 2 синих и 2 зелёных. Игроки А и Б по очереди ставят по одной фишке в одной из вершин 10-угольника. Игрок А хочет получить 5 последовательных вершин всех пяти цветов, а игрок Б хочет этому помешать. Игру начинает Б.
Имеется 8 шаров – по 2 красных, синих, белых и чёрных. Игроки А и Б по очереди прибивают по 1 шару в вершины куба. Игрок А стремится к тому, чтобы нашлась вершина, чтобы в ней и в трёх соседних имелись бы шары всех четырёх цветов, а Б хочет ему помешать.
24955573660
487045-129540
CТАВЬ НА «МИНУС»!
ВЫИГРЫШНЫЕ И ПРОИГРЫШНЫЕ ПОЗИЦИИ
Выигрышная позиция (+) – такая позиция, из которой можно получить заранее определённую проигрышную позицию
Проигрышная позиция (–) – такая позиция, из которой любой ход ведёт в заранее определённую выигрышную позицию
Задача № 9. В куче 25 камней. За один ход разрешается взять 2, 4 или 7 камней из кучи. Проигрывает тот, кто не может ходить.
Решение. Составим таблицу, в которой числа в ячейках будут означать
0 1 2 3 4 5 6 7 8 9 10 11 12
13 14 15 16 17 18 19 20 21 22 23 24 25
0 1 2 3 4 5 6 7 8 9 10 11 12
– – + + + + – + + – + + –
13 14 15 16 17 18 19 20 21 22 23 24 25
+ + – + + – + + – + + – +
Задача № 10. Ферзь стоит на клетке с1. За один ход его можно передвинуть на любое число полей вправо, вверх или по диагонали вправо вверх. Выигрывает тот, кто поставить ферзя на поле h8.
Задача № 11. Имеется две кучи камней: в первой – 7, во второй – 5. За ход разрешается брать любое количество камней из одной кучи, либо поровну из обеих куч. Проигрывает тот, кто возьмёт последний камень.
ИГРЫ-ПРЕСЛЕДОВАНИЯ
Задача № 12. В центре поля, имеющего форму квадрата, находится волк, а в вершинах квадрата – четыре собаки. Волк может бегать по всему полю, а собаки только по сторонам квадрата. Известно, что волк задирает собаку, а две собаки задирают волка. Максимальная скорость каждой собаки в 1,5 раза больше максимальной скорости волка. Докажите что собаки имеют возможность не выпустить волка из квадрата.