11 класс, углублённый уровень. Обзорный практикум к девятой паре: шесть задач по содержанию темы.
34, а не 34 камня
и не 34.. На КЕГЭ ответ читает машина, и здесь так же.Оба игрока в любой момент видят всю позицию и знают все сделанные ходы; ничего скрытого и случайного нет. Ходят по очереди, игра конечна и кончается победой одного из них. Тогда исход определён уже начальной позицией: у одного из игроков есть выигрышная стратегия — правило выбора хода, которое приводит к победе при любой игре соперника, а не только при его ошибке.
Вершины — позиции, рёбра — ходы, корень — начальная позиция, листья — конечные. Одна и та же позиция может встретиться в дереве несколько раз: к ней ведут разные последовательности ходов. Строят дерево сверху вниз, а размечают — снизу вверх: значение вершины известно только после того, как посчитаны все её потомки.
Размечают столбиком от 0 вверх: 0 — П, дальше каждое число смотрит, куда уводят его ходы.
Проигрышные позиции — числа, кратные k + 1. Выигрышный первый ход — взять остаток от деления на k + 1, а потом на каждый ход соперника x отвечать k + 1 − x. Если наоборот, взявший последний камень проигрывает, проигрышные позиции — числа с остатком 1 при делении на k + 1.
В листьях записан результат числом. Игрок, которому нужно больше, в своей вершине берёт максимум из значений потомков; сопернику нужно меньше — он берёт минимум. Уровни чередуются, счёт идёт от листьев к корню; значение корня и есть результат при правильной игре обоих.
Для кучи из n камней с набором ходов M: число партий P(n) = сумма P(n − m) по всем m из M, P(0) = 1; число вершин дерева V(n) = 1 + сумма V(n − m), V(0) = 1. Слагаемое берётся, только когда камней хватает.
Позиция — пара чисел (a, b); ход добавляет один камень в кучу или удваивает кучу. Игра кончается, когда a + b ≥ S. Первым ходом можно получить сумму a + b + 1, 2a + b или a + 2b — значит первым ходом выигрывают ровно при S, не превосходящем наибольшей из этих трёх сумм.
Материалы подготовлены с использованием технологий искусственного интеллекта.