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

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

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

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

10). Ладья стоит на поле al. За ход можно сдвинуть ее на любое число клеток вправо или вверх. Выигрывает тот, кто поставит ее на поле h8. Кто выиграет при правильной игре?

Решение. Разобьем шахматную доску на выигрышные и проигрышные поля (расстановка выигрышных и про­игрышных полей на доске определяется только для одного из игроков).

Что значит позиция выигрышная или проигрышная?

Позиция будет выигрышной для игрока-победителя, если:

а) Завершающая позиция игры для него выигрышная, т. е. он делает последний ход.

б) Из любой выигрышной позиции за один ход нельзя попасть в выигрышную.

в) Из любой проигрышной позиции за один ход можно попасть в выигрышную.

Начинаем с начальной позиции. Ладья стоит на поле al. Поле h8 выигрышное. Пометим его знаком «+». Значит все остальные по­ля последней строки и последнего столб­ца доски проигрышные, т. е. поставим на них знак «-».

 

-	-	-	-	-	-	-	+
-	-	-	-	-	-	+	-
						-	-
						-	-
						-	-
						-	-
						-	-
Ò						-	-

Несложно понять, что поле g7 также выигрышное (с него все ходы ведут в проигрышные поля). Следова­тельно, все остальные поля седьмой горизонтали и седьмого столбца проигрышные и т. д. Расставляя «+» на выигрышные поля, и «-» на проигрышные, мы замечаем, что если ладья стоит на главной диаго­нали, тогда клетка выигрышная, если же она там не стоит, тогда про­игрышная. И тот, кто поставил ладью на поле со знаком «+», выигры­вает, а тот, кто поставил ладью на поле со знаком «-», - проигрывает.

Таким образом выигрывает второй игрок, так как первому игроку первым ходом нужно идти на поле со знаком «-»

-	-	-	-	-	-	-	+
-	-	-	-	-	-	+	-
-	-	-	-	-	+	-	-
-	-	-	-	+	-	-	-
-	-	-	+	-	-	-	-
-	-	+	-	-	-	-	-
-	+	-	-	-	-	-	-
Ò	-	-	-	-	-	-	-

 

Рассмотрим еще одну задачу, где действует данный метод, но где разбиение на выигрышные и проигрышные позиции уже не столь про­сто, как в предыдущей задаче.

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

Решение. Если мы решили использовать метод выигрышных пози­ций, то нам нужно найти эти выигрышные позиции. Чтобы их найти, рассмотрим простейшие случаи.

Простейшая выигрышная позиция для того игрока, кто ее создал (т. е. «сходил» последним): это 1 и 1. Понятно, что в этом случае побе­ждает тот, кто ходит вторым, так как у первого игрока нет хода.

Очевидно, что позиция 2 и 1 выигрышная для первого и проигрыш­ная для второго.

Если 3 и 1, тогда второй вновь с победой, как несложно убедиться простой проверкой, так как есть ровно два хода.

Когда в кучках 3 и 2, победа у первого (убираем 3, делим 2).

Если же 3 и 3, тогда победа вновь возвращается ко второму, что можно показать простым перебором и т. д.

Замечаем закономерность: если в каждой из кучек по нечетному числу конфет, тогда позиция выигрышная для второго.

Если же хотя бы в одной из кучек четное число конфет, то такая позиция выигрышная для первого.

Несложно понять, что когда в обеих кучках по нечетному числу конфет, то за один ход нельзя получить такую же позицию, так как при разделении любого нечетного числа на два слагаемых одно из них будет четным. Однако если хотя бы в одной из кучек четное (ненулевое) чис­ло конфет, то ее несложно разбить на два нечетных слагаемых. Таким образом мы можем разбить все позиции на выигрышные и проигрыш­ные с учетом того, сколько конфет в кучках. И задача выигрывающего делать ход на выигрышные позиции.

После этого уже понятно, кто выиграет в данной по условию игре и как ему этого добиться.

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

Стратегия победителя заключается в том, что он делает ход на «вы­игрышные» поля. Так как первый может сделать ход на «выигрышное» поле, а хода с одного «выигрышного» поля на другое нет, и с любого «проигрышного» поля за один ход можно попасть на «выигрышное», то побеждает начинающий. Своим первым ходом он может съест куч­ку из 21 конфеты, а кучу с 20 конфетами разделить на две, в которых нечетное количество конфет в обеих кучках (например, 19 и 1). За­метим, что последняя позиция, когда две кучки, по одной конфете в каждой, выигрышная, т. е. последний ход сделает первый.

Решим еще одну задачу методом выигрышных и проигрышных по­зиций.

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

Решение. Сначала перенумеруем поля доски. Несложно понять, что одну из шашек можно считать неподвижной, так как в любой случае за один ход, сделанный обоими игроками, расстояние между шашка­ми сокращается не менее, чем на 2 клетки (а именно это и является главным в задаче). Поэтому можно считать, что оба из игроков пере­двигают только одну из шашек. Расставляя знаки «+» и «-» на клетках доски согласно метода решения задачи с конечной позиции, получим следующий рисунок (если первоначально шашки не занимали клеток доски, т. е. между ними было 20 полей):

 

-

+

-

-

+

-

-

+

-

-

+

-

-

+

-

-

+

-

-

+

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

 

Таким образом, становится понятным «выигрышная» стратегия иг­ры первого игрока, чтобы выиграть: он должен делать ходы на клетки со знаком «+», так как с любого поля со знаком «+» нельзя за один ход попасть на поле со знаком «+», а с любого поля со знаком «—» можно, т. е. сделано разбиение всего поля на «выигрышные» и «про­игрышные» поля.

Рассмотрим следующую задачу.

13). Ферзь стоит на поле cl. За ход его можно сдвинуть на любое число полей вправо или на любое число полей вверх или по диагонали вправо-вверх. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?

Решение. Решаем задачу методом выигрышных позиций. Отметим на доске выигрышные и проигрышные поля, начиная с конечной по­зиции.

-	-	-	-	-	-	-	+
-	-	-	-	-	+	-	-
-	-	-	-	-	-	+	-
-	-	+	-	-	-	-	-
+	-	-	-	-	-	-	-
-	-	-	-	+	-	-	-
-	-	-	-	-	-	-	-
-	-	Ф	+	-	-	-	-

Понятно, что h8 - «+». Все поля, с ко­торых можно попасть на h8 за один ход, обозначаем «-». Отсюда поля g6 и f7 со знаком «+». И так далее. Таким образом мы разбили всю доску на выигрышные и проигрышные поля.

После заполнения таблицы мы видим, что выигрывает первый. Он своим пер­вым ходом может занять поле со зна­ком «+», например, с5, и далее ходит на клетки со знаком «+».

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

 

Вот в этом и состоит один из более универсальных методов ре­шения игровых задач: метод выигрышных позиций, т. е. разбиения игрового поля на выигрышные и проигрышные позиции.

Перечислим основные идеи, которые используются при решении задач данным методом:

· начинать поиск решения лучше с клетчатых досок, на ко­торых малое число полей, или с небольшого количества камней, конфет или других предметов, о которых идет речь в задаче;

· разбиение доски на выигрышные и проигрышные поля лучше всего начинать с конечных позиций.

 

Игры – шутки

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

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

Рассмотрим задачу:

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

Решение. Сначала рассмотрим маленькую шоколадку, например, 1x2. Понятно, что здесь выиграет первый, так как всего один ход. А если 1x3? Тогда понятно, что второй, ходов в любом случае, всего два. А если 2x2? Тогда, вновь понятно, что первый, потому что в игре ровно 3 хода. А если шоколадка имеет размеры 1x5? Тогда, после небольшого перебора, замечаем, что выигрывает всегда второй и ходов ровно четыре.

В чем шутка этой задачи? Да в том, что за один ход число кусочков увеличивается ровно на 1, причем совершенно не важно каким образом происходит разлом.

Поэтому при данных условиях (когда шоколадка имеет размеры 6x8) выиграет тот, кто делает «нечетные» разломы, т. е. после хода которого остается четное число кусочков шоколада. Отсюда получаем, что выиграет первый игрок, так как всего будет 48 кусочков шоколадки.

После проведенного анализа для нахождения решения также понят­но, кто выиграет, когда шоколадка будет других размеров, например, 7x9. Ясно, что тогда побеждает второй, так как после его хода все­гда остается нечетное число кусочков и в игре будет сделано ровно 62 хода.

Отсюда можно сделать общий вывод:

Если число кусочков шоколадки четно, тогда побеждает первый, если число нечетно, тогда второй.

Рассмотрим еще некоторые задачи.

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

Решение. И это задача-шутка. Количество возможных ходов для раскладывания кучек: 45 – 3 = 42. Поэтому, как бы ни ходил первый игрок, при его ходе всегда будет четное число кучек. При хо­де же второго игрока количество кучек будет всегда нечетно. Значит, победит первый игрок, так как по окончании игры всегда остается ровно 45 кучек по одному камню в каждой.

16). Малыш и Карлсон делят конфеты. Их всего 101 штука. Если после их дележа количества конфет у каждого из них будут двумя взаимно простыми числами, тогда выиграет Малыш, если же нет, тогда Карлсон. Кто выиграет?

Решение. Это задача-шутка. Здесь всегда выигрывает Малыш, ибо если сумма двух чисел равна 101, то они не могут быть не взаимно простыми (иначе их сумма - 101 - также имела бы среди делителей их общий делитель, а 101 — простое число).

 

Исследования решений некоторых задач в общем виде

А сейчас вернемся к некоторым уже решенным задачам и исследуем решения в общем виде.

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

При решении данной задачи использовалась осевая симметрия: ставя своего слона симметрично слону относительно оси симметрии шахматной доски 8x8, поставленному первым игроком, выигрывает второй игрок.

Исследуем решение данной задачи при различных размерах доски. Если бы доска была размером 7x7 (или 9 х 9), тогда идею осевой симметрии уже нельзя использовать, ибо первый может поставить своего слона в центр и у второго нет хода на это. Необходимо использовать в данном случае центральную симметрию: первый игрок ставит первым своим ходом слона в центр доски, а потом на любой ход противника отвечает симметричным относительно центра ходом. И тогда для первого игрока всегда найдется возможность сделать последний ход.

Итак, в задаче со слонами на шахматной доске возможны следующие случаи:

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

· если квадратная доска имеет нечетные размеры (2k + 1) х (2k + 1), то при решении задачи используем центральную симметрию: после того, как первый ставит своим первым ходом слона в центр доски, то он выиграет, действуя центрально симметрично ходам второго игрока. У него уже есть такая возможность!

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

При решении этой задачи мы располагали точки в вершине правильного 20-угольника и дальше использовали симметрию относительно диаметра.

Ну а если точки расположены не в вершинах правильного 20-угольника, а произволь­но? Тогда ходы будут теми же самыми, толь­ко симметрия будет подразумеваться по номерам вершин. Если первый ходит вначале, соединяя 10-ю и 20-ю точки, второй — i - ю и j-ю, то пер­вый отвечает соединением (20 - i)-й и (20 - j)- йточек. И так далее на каждом последующем шаге.

Ну а если точек не 20, а 2k + 1 (нечетное количество)? Тогда необходимо первому игроку первым ходом провести хорду, соединяющую 1-ю и k + 1 - ю точки, в следствии чего окружность разобьется на две части: в одной – (k – 1) точка, а в другой - k точек. Из этих двух количеств точек одно отличается от другого на единицу. Поэтому при любом ходе второго игрока, для первого игрока найдется ход, симметричный относительно проведенной хорды. И последняя точка, из которой нельзя сделать ход, «достанется» второму игроку.

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

Решение данной задачи основано на дополнении хода противника до числа 6. Выигрывает в данной игре первый, беря из кучки два камня и оставляя 48 камней. Далее после его последующих ходов в кучке будет оставаться соответствен­но 42, 36, 30, 24, 18, 12, 6, 0, таким образом последний камень забирает первый игрок.

Теперь рассмотрим задачу в общем виде и найдем «правило», позволяющее выбрать правильную стратегию при решении задачи..

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

Найдем остаток от деления k на t + 1. Обозначим его a.

· Пусть a ≠ 0. Первый игрок первым ходом должен взять a камней. Второй игрок будет брать за один ход любое количество камней от 1 до t, тогда первый игрок своими ходами должен дополнять ходы противника до t + 1. И тогда последний камень обязательно заберет первый игрок, а значит выиграет. Действительно, если от k отнять a, то получим число, которое нацело делится на t + 1. За один ход второй и первый игроки берут вместе t + 1 камень, причем последним берет первый игрок. Так как k – a нацело делится на t + 1, то первый игрок выиграет.

· Пусть a = 0, тогда по сравнению с предыдущим случаем игроки как бы поменялись местами (число уже сразу нацело делится на t + 1), а поэтому выигрывает второй игрок.

 

Задача № 10. Ладья стоит на поле al. За ход можно сдвинуть ее на любое число клеток вправо или вверх. Выигрывает тот, кто поставит ее на поле h8. Кто выиграет при правильной игре?

 

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

 

Изменим ситуацию в задаче и рассмотрим данную задачу для доски m х n. Исследуем решение данной задачи в общем виде.

 

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

+

-

-

-

-

-

-

-

-

-

-

-

-

-

-

+

-

n -

-

-

-

-

-

-

-

-

-

-

-

-

+

-

-

-

-

-

-

-

-

-

-

-

-

-

-

+

-

-

-

-

-

-

-

-

-

-

-

-

-

-

+

-

-

-

-

-

-

-

-

-

-

-

-

-

-

+

-

-

-

-

m -

-

-

-

-

-

-

-

-

-

+

-

-

-

-

-

-

-

-

-

-

-

-

-

-

+

-

-

-

-

-

-

-

-

-

-

-

-

-

-

+

-

-

-

-

-

-

-

-

-

-

-

-

-

-

+

-

-

-

-

-

-

-

-

-

-

-

-

-

-

+

-

-

-

-

-

-

-

-

-

-

Ò

-

-

-

+

-

-

-

-

-

-

-

-

-

-

 

 

Правое верхнее поле выигрышное. Пометим его знаком «+».Значит все остальные по­ля последней строки и последнего столб­ца доски проигрышные, т. е. поставим на них знак «-». Рассуждая аналогично предыдущей задаче, расставим выигрышные позиции (знаки «+») в диагонали клеток, ведущих с правой верхней клетки. Тогда все остальные поля отмеченных горизонталей и отмеченных столбцов проигрышные (m горизонталей и m столбцов).

Теперь очевидно, что при правильной игре выигрывать будет первый игрок: первым ходом он должен пойти на n – m (n > m) полей вправо (или m – n полей вверх в случае m > n), попав на поле выигрышной позиции. Далее второй игрок своим ходом будет попадать только на проигрышные позиции, с которых первый игрок должен возвращаться на диагональ выигрышных позиций.

Используемая литература:

1) Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки. Киров: АСА, 1994.

2) Гусев В.А., Орлов И.А., Розенталь А.Л. Внеклассная работа по математике в 6-8 классах. М.: Просвещение, 1984.

3) Петров Н.Н. Математические игры. Ижевск: УдГУ, (1 изд.) 1994.

4) Яглом И.М. Две игры со спичками // Квант. 1971. №2.

5) Л. М. Лихтарников. Задачи мудрецов. М.: Просвещение, 1996.

6) Т. П. Бахтина. Готовимся к олимпиадам, турнирам и математическим боям. Минск: АВЕРСЭВЬ, 2004.

7) А. В. Спивак. Тысяча и одна задачи по математике. М.: Просвещение, 2002.