Лекция 12: Графы - 2 (стр. 20 )

Задача 1. Двое по очереди кладут пятаки на круглый стол так, чтобы они не накладывались друг на друга. (Проигрывает, как обычно, тот, кто не может сделать ход.)
Решение: Как бы так первому игроку сделать свой ход... куда можно положить пятак на пустом круглом столе??? А давайте его в центр положим! Внимание: после такого хода расположение пятаков на столе стало центрально симметричным(!!!) Теперь давайте отвечать на каждый пятак второго игрока центрально симметричным ему пятаком. Почему же мы стратегия никогда не обломается (и мы не проиграем)? Облом стратегии означает ровно одно: второй положил куда-то пятак, а мы не смогли положить пятак в симметричное место (там уже что-то лежит). После нашего предыдущего хода позиция была симметричной (из симметричности не только сделанных ходов, но и самого стола), а место, куда второй положил пятак было свободно. Центрально симметричное ему место, куда мы хотим положить свой пятак, тоже было свободно. Но не мог же второй занять это место своим пятаком (это тоже важно заметить, не во всех задачах так будет!!!). Значит, не может быть так, чтобы нам некуда было положить свой пятак. Первый выигрывает.

Задача 2. Двое по очереди ставят слонов в клетки шахматной доски так, чтобы они не били друг друга (цвет слонов значения не имеет). Все как обычно.
Решение: Ну тут, казалось бы, без фокусов. Доска имеет размер 8x8, и никакая клетка центром симметрии не будет. Поэтому второй может всегда отвечать на ходы первого симметричными ходами и выиграет. НО: Пусть первый игрок поставил слона на диагональ доски. Если второй игрок ставит своего слона в центрально симметричную клетку, то он окажется на той же диагонали... как раз под боем слона, поставленного первым игроком! Действительно, бывает так, что очередному симметричному ходу мешает ход, только что сделанный противником (поэтому надо внимательно следить за такими ситуациями!).
Выход из положения - применить симметрию не центральную, а осевую (относительно средней линии доски). Нетрудно убедиться, что клетку, симметричную своей позиции относительно оси, слон никогда не бьет. После каждого хода второго вся позиция симметрична, в т. ч. расположение не бьющихся полей; ход первого тоже не ставит под бой поле, симметричное тому, куда он был сделан. Поэтому симметричное (теперь - относительно оси!) поле не бьется. Второй всегда может сделать ход и выигрывает.

Задача 3. На доске 10x12 можно за ход вычеркнуть одну линию (горизонталь или вертикаль, т. е. строку или столбец) если в ней еще есть одна невычеркнутая клетка.
Решение: (Нет, это не дежа вю, а иллюстрация, как можно искать стратегию там, где ее нет. Причем это еще и окажется не менее красивым решением, чем первоначальное!) Второй может использовать центральную симметрию (множество клеток, центрально симметричных линии - линия). После каждого хода второго расположение линий, которые еще можно вычеркнуть, центрально симметрично, поэтому стратегия работает и на каждый следующий ход. Идиотский ход эта стратегия разбирает, как общий случай (убедитесь сами!).

Задача 4. Есть две кучки камней, по 17 в каждой. За ход можно взять несколько камней, из одной кучки.
Решение: И это тоже симметрия! Выигрывает второй - он берет из другой кучки столько камней, сколько первый взял из одной. При этом после каждого хода второго камней в обеих кучках будет поровну - поэтому стратегию можно продолжать.
А если бы кучки были неравны, то выиграл бы первый. Первым ходом он взял бы из большей кучки столько камней, чтобы уравнять ее с меньшей, а далее пользовался бы изложенной выше стратегией.

(!) На самом деле, нередкое явление: в зависимости от исходных данных одна и та же стратегия приносит успех то первому, то второму игроку.

Задача 5. Есть одна кучка из 48 камней. За ход можно взять из нее от 1 до 3 камней.
Решение: Еще один распространенный вариант симметрии. Сколько бы не взял первый игрок, второй может взять несколько камней, дополняя его число до четырех. Т. о., за каждую пару ходов первый и второй берут 4 камня. Каждый раз после хода второго число камней в кучке делится на 4, а после хода первого - не делится. При этом 0 камней (т. е. ситуация, когда нельзя сделать ход) неминуемо достанется первому игроку, т. к. 0 делится на 4. Выигрывает второй.
Опять же, если бы число камней в кучке не делилось бы на 4, выиграл бы первый. Сначала он взял бы столько камней, чтобы число оставшихся делилось на 4, затем воспользовался бы нашей симметрией.

Анализ выигрышных позиций.
Бесспорно, самый мощный и универсальный способ решения заач на игры - поиск выигрышных позиций. Здесь мы будем называть выигрышной ту позицию, которую выгодно оставлять после своего хода, а проигрышной, соответственно, ту, которую невыгодно (в согласии с одной половиной методической литературы и в противоположность другой половине :-) Тогда финальная позиция, из которой уже нельзя сделать ход - выигрышная. Основные свойства позиций таковы:
1.) каждая позиция - либо выигрышная, либо проигрышная (промежуточных вариантов нет!);
2.) из выигрышной позиции можно пойти только на проигрышную;
3.) из любой проигрышной позиции можно пойти на выигрышную.
Тогда, если начальная позиция - проигрышная, выигрывает первый, если выигрышная - второй. Стратегия одинакова: каждый раз ходить на выигрышную позицию. Тогда противник должен будет походить на проигрышную позицию (свойство 2), а мы опять сможем пойти на выигрышную (свойство 3).

Задача 1. "Хромая ладья" может ходить по прямой вправо или вверх. Исходно она стоит в нижнем левым углу доски. Играют двое. Выигрывает тот, кто поставит ладью в верхний правый угол.
Решение: Исходно ладья стоит на главной (в данном случае - главной) диагонали доски. Первый игрок своим ходом уводит ее с диагонали в сторону. Тогда второй игрок может вернуть ладью обратно на диагональ (посмотрите, как). Потом первый опять уведен ее с диагонали (ходов с главной диагонали на нее же нет), а второй... опять сможет вернуть и т. д. Так так клетка назначения лежит на главной диагонали, то на ней ладья обязательно окажется после хода второго - и второй выигрывает.
Читаем между строк: "множество выигрышных позиций - это главная диагональ".

Анализ с конца: как же искать выигрышные позиции, если угадать их не удалось? Можно просто последовательно разобрать все позиции, начиная с последней (желательно, для удобства, чтобы множество позиций умещалось на двумерной доске/таблице). Финальная позиция выигрышная. Поэтому все, с которых на нее можно пойти - проигрышные. Теперь должны образоваться позиции, с которых можно пойти только на проигрышные - они будут выигрышными. Все позиции, с которых можно пойти на какую-то из этих выигрышных - проигрышные и т. д., пока не дойдем до начальной позиции.

Задача 2. "Хромой король" может ходить на 1 клетку вправо, вверх или вверх-вправо. Исходно он стоит в нижнем левым углу доски. Играют двое. Выигрывает тот, кто поставит короля в верхний правый угол.
Решение: Будем отмечать позиции на доске ("+" - выигрышная, "-" - проигрышная). Позиция в верхнем правом углу - финальная - выигрышная. 3 соседние, с которых можно на нее пойти - проигрышные (см. табл.).

? ? ? ? ? ? - + ? ? ? ? ? ? - - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? - + - + ? ? ? ? - - - - ? ? ? ? ? ? - + ? ? ? ? ? ? - - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? - + - + - + ? ? - - - - - - ? ? ? ? - + - + ? ? ? ? - - - - ? ? ? ? ? ? - + ? ? ? ? ? ? - - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

- + - + - + - + - - - - - - - - - + - + - + - + - - - - - - - - - + - + - + - + - - - - - - - - - + - + - + - + - - - - - - - -

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

Задача 3. Есть две кучки камней: в одной 6, в другой 5. За ход можно взять несколько камней из одной кучки или поровну камней из обеих кучек.
Решение: Занесем позициии в таблицу, где по двум осям будем отмечать количество камней в двух кучках. Финальная позиция (0,0) - нижний левый угол, начальная - верхний правый. Возможные переходы: влево по горизонтали, вниз по вертикали или влево-вниз по диагонали на любое количество клеток. Если мы отметим финальную выигрышную позицию и все, откуда на нее можно пойти, то получим картину, как на табл. слева. Результат окончательного нахождения позиций можно видеть на табл. справа. Опять начальная позиция проигрышная и выигрывает первый.

5 - ? ? ? ? - ? 4 - ? ? ? - ? ? 3 - ? ? - ? ? ? 2 - ? - ? ? ? ? 1 - - ? ? ? ? ? 0 + - - - - - - x 0 1 2 3 4 5 6

5 - - - + - - - 4 - - - - - - - 3 - - - - - + - 2 - + - - - - - 1 - - + - - - - 0 + - - - - - - x 0 1 2 3 4 5 6