МАЛЫЙ МЕХМАТ МГУ
Занятие 7. Математические игры
Под понятием математической игры мы понимаем игру двух соперников, обладающую следующим свойством. В каждый момент игры состояние характеризуется позицией, которая может изменяться только в зависимости от ходов игроков. Некоторые позиции являются выигрышными для одного из игроков. Добиться выигрышной для себя позиции и есть цель каждого. Иногда игры допускают ничью. Это означает, что ни один из игроков не может добиться выигрышной для позиции, или некоторые позиции объявляются ничейными.
Например, шахматы, шашки, крестики–нолики являются математическими играми. А игра в кости (домино), большинство карточных игр математическими играми не являются, так как состояние игры зависит не только от ходов соперника, но и от расклада.
В математических играх существуют понятия выигрышной стратегии, то есть набора правил (можно сказать, инструкции или алгоритма) следуя которым, один из игроков обязательно выиграет (не зависимо от того, как играет его соперник) и ничейной стратегии, следуя которой один из игроков обязательно добьётся либо выигрыша, либо ничьей.
В любой математической игре существует либо выигрышная стратегия для одного из игроков, либо ничейные стратегии для обоих (если игра допускает ничью). В зависимости от этого игра называется выигрышной для первого или второго игрока, или ничейной.
Например крестики–нолики (на доске 3×3) являются ничейной игрой. К какому из перечисленных случаев относятся шахматы и шашки неизвестно. Хотя стратегия (либо выигрышная, либо ничейная) в этих играх существует, она не найдена, поэтому соревнования по этим играм пока представляют интерес.
Игра в кошки–мышки (задача 9 занятия 6), является выигрышной для мышки в случае а) и для кошки в случае б). Действительно, раскрасим узлы доски в два цвета в шахматном порядке. После каждого хода кошки она оказывается с мышкой в узлах разного цвета, поскольку любой ход меняет цвет. Значит, чтобы всё время убегать от кошки, мышка может ходить как угодно, лишь бы не прыгать самой в лапы кошке. В случае же б) имеется ход, позволяющий кошке не сменить цвет (ход по наклонной линии в левом верхнем углу). Сделав этот ход, кошка без труда загонит мышку в любой другой угол и поймает (докажите это строго сами).
Большинство из задач этого листка представляют собой правила некоторой математической игры. Ваша цель - определить, является ли игра выигрышной (и для какого из игроков) или ничейной и предъявить соответствующую стратегию. Заметим, что требуется не только уметь выигрывать, но и составить «инструкцию», следуя которой, выиграет любой человек. Для начала предлагаем поиграть в эти игры между собой.
| 1. |
Спички. В кучке лежат 100 спичек. Двое по очереди берут спички из кучки. За один ход разрешается взять одну или две спички. Взявший
последнюю спичку выигрывает. |
| 2. | Щёлк.
Доска представляет собой прямоугольную шоколадку, разделённую бороздками на дольки. Ход состоит в том, что игрок выбирает любую ещё не съеденную дольку и съедает все дольки, расположенные от выбранной выше и левее, иными словами съедает уголок. Съевший последнюю дольку, проигрывает. Рассмотрите случаи размера шоколадки а) 2×8; б) 8×8. |
| 3. |
|
| 4. | Лото–15.
На столе лежат 9 карточек с цифрами от 1 до 9. Двое по очереди
берут карточки. Выигрывает тот, у кого на руках окажутся три
карточки с суммой 15. |
| 5. | Ним.
Имеются несколько кучек камней. Двое по очереди берут камни. За
один ход разрешается взять любое количество камней, но только из
одной кучи. Выигрывает взявший последний камень. Рассмотрите случаи начального количества камней: а) две кучки по 10 камней;
б) три кучки по 10 камней. |
| 6. | Кони. На доске 3×3 стоят два белых и два чёрных коня. Можно ли, двигая коней по правилам шахмат (в любом порядке) из позиции а) получить позицию б)?
|
| 7. |
|
| 8. | Сеанс одновременной игры. Остап Бендер провел сеанс одновременной игры в шахматы с
гроссмейстерами Гарри Каспаровым и Анатолием Карповым. С одним из
соперников он играл белыми фигурами, а с |
Крестьяне и свиньи.
Двое крестьян (К) ловят двоих свиней (С) на доске (рис. 8). Ходят
по очереди. За каждый ход, ходит либо один из крестьян, либо одна
из свиней. Смогут ли крестьяне поймать свиней?
Ладьи.
На доске 2×8 стоят две белых и две чёрных ладьи.
Двое ходят по очереди.
а) За один ход первый передвигает одну из белых ладей на любое количество полей вправо, а