«Как играть, чтобы не проиграть» - это тематический сборник, в который включены выигрышные стратегии игр «Морской бой» и «Быки и коровы», идеи решения различных вариаций задач «Ним» и подборка задач-игр для самостоятельного решения для подготовки к олимпиадам и конкурсам.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Агаханов Н.Х. Районные олимпиады. 6 – 11 классы / Н.Х. Агафонов, О.К. Подлипский. –М.: Просвещение, 2010. – 192 с.: ил. – (Пять колец)
2. Гик Е.Я. Занимательные математические игры.   М.: «Знание», 1987 г. – 169 с. (Нар. Университет. Естественнонаучный факультет). 
3. Горбачёв Н.В. Сборник олимпиадных задач по математике. – М.: МЦНО, 2004. – 560с.

Оглавление

17

Терминология

2

1. Игра «Морской бой»

Классический морской бой – самый популярный вариант морского боя. Каждый из игроков рисует на клетчатом листе бумаги две доски размером 10х10. На первой из них он расставляет свои корабли, а на второй разгадывает расположение корабле противника. В состав флотилии входят десять кораблей: один линкор (корабль 4х1), два крейсера (3х1), три эсминца (2х1) и четыре катера (1х1). Корабли могут занимать любые поля доски, но не должны касаться друг друга ни сторонами, ни углами.

После размещения флота игроки начинают по очереди стрелять по неприятельской территории, т. е. называть поля доски – а2, б5, и8 и т. д. (горизонтали доски обозначают числами от 1 до 10, а вертикали – русскими буквами от а до к). После каждого выстрела игрок получает от партнёра следующую информацию: «попал», если выстрел пришёлся по полю с кораблём; «убил», если это последнее поле, и, наконец «мимо», если поле пустое. В первых двух случаях игрок производит ещё один выстрел, и так до первого промаха, после чего очередь хода передаётся партнёру. Побеждает тот, кто первым потопит все десять кораблей противника 

3

Ответы.

1. Второй.
2. Если 48 камней – выигрывает второй, если 55 камней – выигрывает – первый.
3.  Второй.
4. Первый.          
5. Первый.
6. 0189.

7. 0981.
8. 0615.
9. 1720.

16

        Задача 6. В игре были сделаны ходы:

1985     1 бык, 2 коровы

5147     1 бык, 0 коров

4801     0 быков, 3 коровы

6870     0 быков, 2 коровы

        По сделанным ходам, отгадайте, какое число было задумано.

        Задача 7. В игре были сделаны ходы:

3086     1бык, 1корова;

7914     1бык, 1корова;

0794     1бык, 1корова;

6491     1бык,  1корова;

1947     1бык, 1корова.

        Отгадайте, какое число было задумано.

Задача 8. В игре были сделаны ходы:

0376    1 бык, 1 корова;
5089    0 быков, 2 коровы;
6190    0 быков, 3 коровы;
5489    0 быков, 1 корова;
4075    1 бык, 1 корова.

        Отгадайте, какое число было задумано.

Задача 9. В игре были сделаны ходы:

3140    1 бык, 1 корова;

7016    0 быков : 3 коровы;

3487    0 быков : 1 корова;     

0274    0 быков : 3 коровы;

        Отгадайте, какое число было задумано.

15

Стратегия игры. Для определения расположения линкорна стреляем по полям противника по одной из предложенных схем (24 крестика следуют друг за другом  через три поля вдоль каждой вертикали и горизонтали).

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

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

4

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

Итак, построение выигрышной стратегии игры заключается в следующем:

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

5

В этом случае стратегия не изменится, просто нужно будет учесть, что число фишек равно m - 1, а не m. Для победы будет достаточно взять предпоследнюю фишку, оставив на столе всего одну.

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

Задача 1. Есть две кучки камней, по 17 в каждой. За ход можно взять несколько камней, из одной кучки. Проигрывает тот, кому не достанется камней. Кто выиграет при «правильной игре»? А если в кучках будет 19 и 23 камня соответственно? Кто и как должен играть?

Задача 2. Есть одна кучка из 48 камней. За ход можно взять из нее от 1 до 3 камней. Кто выиграет при «правильной игре»? А если в кучке будет 55 камней? Кто выиграет?

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

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

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

14

Выигрышная стратегия для этой игры — это общая стратегия, которая применима к бесконечному множеству аналогичных игр. Эта стратегия формулируется так. Поделим m на n + 1 и определим остаток от деления. Он будет находиться в интервале от 0 до n. Возможны два случая:

1. Остаток от деления равен 0. В этом случае существует выигрышная стратегия для второго игрока, который должен оставлять на столе число фишек, кратное n + 1. Для этого на каждом ходу, если первый игрок берет ρ фишек (0 < ρ < n + 1), второй должен брать n + 1 - ρ фишек. Это число всегда положительно, так как находится на интервале от 0 до n.

2. Остаток от деления равен r (0 < r < n + 1).В этом случае существует выигрышная стратегия для первого игрока. На первом ходу он должен взять r фишек, оставив на столе число фишек, кратное n +1. Теперь он может действовать подобно второму игроку из первого случая. Иными словами, если второй игрок берет ρ фишек (0 < ρ < n + 1), первый должен взять n + 1 – ρ фишек.

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

13

2. Игра «Быки и коровы»

В эту игру играют вдвоём. Каждый задумывает четырёхзначное число с разными цифрами, которые должен отгадать партнёр. После каждой попытки соперник проводит анализ ответа и сообщает о степени совпадения названного числа с задуманным, которое характеризуется количеством «коров» и «быков». Если задуманное и названное число имеет общие цифры, стоящие на одних и тех же местах, то такую ситуацию называют «быком». Если общие цифры есть, но стоят они на разных местах, то это «корова». Например, если задумано 5239, а названо 2735, то ответ будет «1 бык 2 коровы» (1б 2к). Цифра 3 имеется в обоих числах и стоит на одинаковых местах (1б), цифры 2 и 5 общие, но стоят на разных местах (2к), цифры 7 и 9 не являются общими.

 Игра заканчивается в тот момент, когда на очередной свой ход получен ответ «4б». Выигрывает тот, кто быстрее отгадает число противника.

6

Стратегия игры. Покажем выигрышную стратегию на примере.

Предположим, что на первый вопрос о числе 1234 получен ответ одна корова. Это значит, что в данном числе угадана одна цифра, которая не стоит в своём разряде. Вторым вопросом была комбинация 5678. И тут удача – два быка и одна корова. Следовательно, угаданы ещё три цифры, две из которых в задуманном числе стоят в своём разряде. Стратегия третьего хода следующая: угаданы три цифры, нужно определить их расположение. Точно известно, что цифры 9 и 0 отсутствуют в загаданном числе. Для следующей комбинации числа берутся две цифры из второй комбинации, но ставятся они на другие места и доставляются цифры 0 и 9. Предлагаем сопернику следующее число: 7890, от которого получен ответ – 2 коровы. Делаем вывод, что определили 2 быка – позиции двух цифр в числе: цифра 7 – на третьем месте, а 8 на четвёртом. Рассуждение продолжаем дальше. Из второй комбинации чисел известно, что цифры 5 или 6 точно есть в загаданном числе. Уберём одно из них, а второе поставим на другое место. Ещё оду цифру возьмём из первой комбинации чисел, тут без разницы какое – чистое везение. Получаем, например, такую комбинацию цифр – 4578. Число отгадано, ответ – четыре быка!

7

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

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

Задача - игра 4.  «Кто раньше назовет число 70?».

Играют двое. Один называет любое целое число от 1 до 9 включительно. Второй прибавляет к названному числу любое целое число от 1 до 9, какое захочет, и называет сумму. К этой сумме первый снова прибавляет любое целое число от 1 до 9 и называет новую сумму и т. д. Выигрывает тот, кто раньше назовет число 70.

Стратегия игры.  В этой игре начинающий, будем так и называть его: «Игрок А», всегда проигрывает, если его партнер, которого условимся называть «Игрок В»,  играет правильно. Нетрудно обнаружить способ игры «Игрока В», иначе говоря, стратегию «Игрока В», которая обеспечивает ему победу: «Добавляй до числа, кратного 10!» Если, например, «Игрок А» назвал 4, «Игрок В» прибавляет 6 и называет сумму 10. Если «Игрок А» прибавит теперь 9 и назовет сумму 19, то «Игрок В» прибавит 1 и назовет сумму 20. Ясно, что, как бы ни играл «Игрок А», «Игрок В» при такой стратегии раньше доберется до суммы 70 и выиграет. Разумеется, если он хоть раз ошибется, то этой же стратегией сможет воспользоваться «Игрок А» и одержит победу.

12

Задача - игра 2. В одной кучке лежит 71 камень, а во второй - 72 камня. За один ход разрешается брать любое количество камней, но только с одной кучки. Проигрывает тот, кому нечего будет брать. Кто выигрывает при правильной стратегии - тот, кто начинает или другой игрок?

Стратегия игры. При правильной стратегии выигрывает первый игрок. Его стратегия: первым ходом он должен сравнить количество камней в стопках, то есть взять с второй кучки 1 камень. Каждый последующий ход должен быть «симметричный» ходу второго игрока, то есть если второй игрок берет n каминей с одной кучки, то первый игрок должен взять также n камней, но с другой кучки. Таким образом, если может сделать ход второй игрок, то может сделать ход и первый. Поскольку после каждого хода количество каминей уменьшается, то наступит момент, когда второй игрок не сможет сделаеть ход (в одной из кучек камней не останется) и проигрывает.

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

Стратегия игры. Для удобства предположим, что все

11

Приведем один пример. Ходы и ответы на них будем записывать в таблице.

Итак, построение выигрышной стратегии игры заключается в следующем:

1. Вопрос нужно задавать так, чтобы ответ на него давал максимальное количество информации.
2. Формировать вопрос необходимо так, чтобы вероятности различных ответов были по возможности близкими.
3. Вопрос должен быть таким, чтобы ответ на него не содержал информацию, полученную ранее из предыдущих вопросов.

8

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

         Существует несколько разновидностей игр, в которых двое играющих – игрок «А» и игрок «В», руководствуясь определёнными правилами, по очереди вынимают то или иное число предметов из одной или нескольких кучек – побеждает тот, кто берет последний предмет. Простейшая такая игра – это игра с одной кучкой фишек, и сделать ход в ней – значит, взять из кучки любое число фишек от 1 до m включительно. Эту игру изобрел Леонардо Пизано в 1202 г., её называют математическая игра «Баше» (современное название – «Ним»).

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

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

Стратегия игры: когда в начальной позиции на столе 20 фишек, первый игрок будет всегда выигрывать,

9

если будет брать первым ходом 2 фишки и затем всегда  оставлять на столе количество фишек, кратное 3 (если второй игрок снимает одну фишку, первый игрок должен взять две, и наоборот). В этой игре первый игрок имеет преимущество, для него существует выигрышная стратегия.

Изменение начального количества фишек может частично повлиять на эту стратегию и даже на то, какой из игроков будет иметь преимущество. Выигрышная стратегия состоит в том, чтобы оставлять на столе число фишек, кратное 3. Чтобы узнать, на чьей стороне преимущество, достаточно разделить начальное количество фишек на 3 и посмотреть, каков остаток от деления. Если остаток равен 2 (как в исходном случае), то первый игрок всегда выигрывает, если берет первым ходом 2 фишки, а затем оставляет на столе число фишек, кратное 3 (если противник берет одну фишку, первый игрок берет две, и наоборот). Если остаток от деления равен 1 (например, число фишек равно 19, 25, 100 или 2017), то первый игрок также выигрывает. Для этого достаточно взять первым ходом одну фишку. Наконец, если остаток равен 0 (количество фишек делится на 3), то выигрывает второй игрок: ему нужно взять две фишки, если первый игрок взял одну, и наоборот. В этом случае первый игрок никогда не сможет оставить на столе число фишек, кратное 3.

                             10