Методы решения игровых задач (стр. 2 )

Итак, если число камней делится на 6, то выигрывает второй, если не делится, то первый. Докажем это.

Пусть у нас 6t камней. После первого хода игрока, начинающего игру, второй делает ход, после которого остается 6t - 6 камней, т. е. число камней в кучке уменьшилось на 6. Несложно понять, что послед­ний камень возьмет игрок, делающий второй ход, и также понятно, что у него всегда есть возможность сделать ход.

Пусть у нас 6t+a, где 1 < а < 5, камней. Тогда начинающий первым своим ходом убирает все, что «мешает», т. е. а камней, и остается всего 6 t камней, т. е. сводит игру к рассматриваемому выше случаю, где он уже второй игрок. Значит в этом случае побеждает игрок, делающий первый ход.

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

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

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

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

Начинающий первым ходом говорит число 2, и при каждом следу­ющем ходе будет говорить число, которое больше предыдущего (т. е. сказанному им на предыдущем ходу) ровно на 6. Итак на втором ходу он говорит число 8, на третьем - 14, ..., на девятом - 50.

Второй игрок не сможет помешать начинающему, так как макси­мальное число, которое он может прибавить к сказанному первым иг­роком — это 5, а минимальное - это 1 (а разность между числами, произносимыми первым, - 6).

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

Пусть лежат 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), а поэтому выигрывает второй игрок.

И еще некоторые задачи:

8).  Двое играют в такую игру: за один ход игрок может прибавить к имеющемуся числу любую из девяти ненулевых цифр, от 1 до 9, и сообщить получившуюся сумму своему партнеру, который делает аналогичный ход. Вначале дано число 0. Выиграет тот, кто первым получит в сумме а) 100; б) 66. Кто выигрывает при правильной игре? Как нужно играть, чтобы выиграть?

(Эта игра содержится в собрании задач по «занимательной» математике, составленном Баше в 1612г.)

Решение: а) Выигрывает второй, так как он может называть числа, которые будут делиться на 9 + 1 = 10, т. е. при своем ходе завершать каждый десяток.

б) Понятно, что сейчас выигрышная стратегия есть уже у первого игрока. Остаток от деления числа 66 на 9 + 1 = 10 равен 6. Первый игрок первым ходом должен назвать число 6, а потом последующими ходами будет называть числа, оканчивающиеся на 6. После седьмого хода им будет названо число 66.

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

Решение. Остаток от деления числа 15 на 3 + 1 = 4 равен 3. Начинающему надо, добиться того, чтобы последний карандаш взял противник, поэтому первым ходом он должен взять не 3 карандаша (остаток от деления), а 2 (1 карандаш – противнику!) Затем каждым последующим ходом будет дополнять количество карандашей, взятых вторым игроком, до 4.

После первого хода 1 - го игрока на столе останется 13 карандашей, после второго хода — 9, после третьего — 5, после четвертого — 1. Следовательно, последний карандаш берет второй игрок.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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