МАЛЫЙ МЕХМАТ МГУ

Кружок 6 класса

Руководитель Степан Львович Кузнецов
2014/2015 учебный год

Группа «А»

Группа «Б»

Группа «К» (ст. преп. Л. Н. Колотова)

Группа «В» (ст. преп. А. С. Воропаев)

Группа В (старший преподаватель А. С. Воропаев)

Занятие 22 (11 апреля 2015 года). Математика игр

Выигрышная позиция — такая, получив которую, можно играть так, чтобы выиграть,чтобы не делал соперник.

Проигрышная позиция — такая, получив которую, вы проиграете, если только соперник не ошибётся.

Игры, о которых пойдёт речь сегодня, такие:

Для двух игроков.
Оба игрока знают об игре всё, кроме того, как будет ходить второй игрок. (Например, многие карточные игры не подходят — в них не только часто неизвестна рука второго игрока, но ещё и присутствует случайность.)
В игре нет ничьи, и она не может продолжаться вечно.
Каждый ход выбирается из конечного числа вариантов.

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

0.

Какая из игр с прошлых двух занятий не подходит под условия?

1.

Найдите все выигрышные и проигрышные позиции в игре:
Имеются две кучки по 9 камней. За ход можно взять любое количество камней, но только из одной кучки. Выигрывает тот, кто возьмёт последний камень.

2.

Докажите:

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

3.

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

а): На шахматной доске 8×8 в левом нижнем углу стоит король. Игроки по очереди передвигают её на 1 клетку либо вверх, либо вправо, либо вправо-вверх. Выигрывает тот, кто поставит фишку в правый верхний угол.
б): Первый игрок называет целое число от 2 до 9. Второй умножает это число на произвольное целое число от 2 до 9. Затем первый умножает результат на любое целое число от 2 до 9, и так далее. Выигрывает тот, кто первым получит произведение больше 1 000.
в): Есть четыре кучки: с 1 камнем, с 3, с 5 и с 7. За ход можно взять любое количество камней из любой одной кучки. Выигрывает тот, кто забирает последний камень.