Н.С. Белов | Теория игр. Пособие для подготовки к олимпиадам по математике (2025) [PDF]

Игры и стратегии – отдельный класс математических задач.
Математические игры отличаются от обычных тем, что в них можно заранее определить исход игры. В таких играх предполагается, что игроки не делают ошибок, т. е. играют наилучшим образом. Под понятием математической игры мы понимаем игру двух соперников, обладающую следующим свойством. В каждый момент игры состояние характеризуется позицией, которая может изменяться только в зависимости от ходов игроков. Для каждого из игроков некоторые позиции объявляются выигрышными. Добиться выигрышной для себя позиции и есть цель каждого. Иногда игры допускают ничью. Это означает, что ни один из игроков не может добиться выигрышной для него позиции, или некоторые позиции объявлены ничейными.
Например, шахматы, шашки, крестики/нолики являются математическими играми. А игры в кости, домино, большинство карточных игр математическими играми не являются, так как состояние игры зависит не только от ходов соперника, но и от расклада или результата бросания кости.
В математических играх существуют понятия выигрышной стратегии, т. е. набора правил (можно сказать, инструкции или алгоритма), следуя которым, один из игроков обязательно выиграет (не зависимо от того, как играет его соперник), и ничейной стратегии, следуя которой один из игроков обязательно добьётся либо выигрыша, либо ничьей.
В любой математической игре существует либо выигрышная стратегия для одного из игроков, либо ничейные стратегии для обоих (если игра допускает ничью). В зависимости от этого игра называется выигрышной для первого или второго игрока, или ничейной.

Содержание

1. Введение
1. ИГРЫ-ШУТКИ
1.1. Примеры решения задач
2. ИГРЫ, ИСПОЛЬЗУЮЩИЕ СИММЕТРИЮ
2.1. Примеры решения задач
2.2. Задачи для самостоятельного решения
3. ИГРЫ, В КОТОРЫХ СТРАТЕГИЯ – ДОПОЛНЕНИЕ
3.1. Примеры решения задач
3.2. Задачи для самостоятельного решения
4. РАЗНЫЕ ИГРЫ
4.1. Поиск стратегии с конца
4.2. Разбиение на пары
4.3. Передача хода
5. ЗАДАЧИ С «ВСЕРОССИЙСКОЙ ОЛИМПИАДЫ ШКОЛЬНИКОВ»
5.1. Задачи с решениями
5.2. Задачи для самостоятельного решения
6. ОТВЕТЫ, УКАЗАНИЯ, РЕШЕНИЯ
6.1. Игры, использующие симметрию
6.2. Игры, в которых стратегия – дополнение
6.3 Поиск стратегии с конца
6.4 Разбиение на пары
6.5. Передача хода
6.6 Задачи с ВсОШ
Литература