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

Занятие 8. Выигрышные позиции

Рассматриваем игры, в которые играют два человека, поочередно совершая ходы. Правила симметричные, то есть игроки делают одинаковые ходы. Во всех задачах (кроме последней) проигрывает тот, кто не сможет сделать очередного хода. Также предполагаем, что игра заканчивается через конечное число ходов (то есть рано или поздно один из игроков проигрывает).

1.	В коробке лежат n спичек. За ход можно взять 1, 2, 3 или 5 спичек. Кто выиграет при правильной игре?

Определение. Разделим все возможные позиции в игре на выигрышные и проигрышные следующим образом:

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

2.	Докажите, что все позиции рассматриваемых нами игр можно однозначно поделить на выигрышные и проигрышные: если начальная позиция выигрышная, то выигрышная стратегия существует у первого игрока, а если проигрышная, то у второго.
3.	На шахматной доске стоит ферзь, которым разрешено ходить только влево, вниз или по диагонали влево-вниз. Найдите все проигрышные позиции.
4.	В двух кучках лежат m и n камней. За ход можно брать один камень из любой кучки или по одному камню из каждой. Кто выигрывает при правильной игре?

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

5.	Докажите, что число Гранди терминальной позиции равно нулю. Докажите, что в любой игре вида (*) можно однозначно найти числа Гранди всех позиций. Докажите, что если число Гранди начальной позиции равно 0, то выигрывает второй игрок, иначе — первый.

6.	Найдите числа Гранди всех позиций в задачах 1 и 3.

Определение. XOR-суммой x (+) y двух целых неотрицательных чисел x и y будем называть число, полученное следующим образом: представим x и y в двоичной системе счисления; каждый двоичный разряд XOR-суммы будет равен 1, если ровно у одного из чисел x и y в этом разряде 1, и 0 — если оба равны 0 или оба — 1. Другими словами, XOR-сумма представляет собой сложение в двоичной системе счисления без переносов в следующий разряд. (Обозначение (+) не является общепринятым. Чаще пишут плюс в кружочке или как-нибудь ещё. Мы используем обозначение (+) из-за того, что (+) легко набрать на клавиатуре компьютера.)

7.	Вычислите а) 3 (+) 2; б) 5 (+) 7; в) 170 (+) 85.

Теорема. Пусть есть две игры. Каждый ход игрок может сделать либо в одной из этих игр, либо в другой. Проигрывает тот, кто не может сделать хода. Каждая позиция в этой составной игре есть пара (p,q), где р — текущая позиция в первой игре, а q — во второй. Тогда SG((p,q)) = SG(p) (+) SG(q).

8.	Докажите эту теорему.
9.	Есть два коробка. В каждом по 70 спичек. Из первого можно брать 1 или 2 спички за ход, а из второго — 1, 2 или 3 спички за ход. Кто выигрывает?
10.	В кучке а) 13; б) 15 камней. Каждым ходом игрок может разбить на две кучки любую кучку, в которой есть хотя бы три камня. Кто выигрывает?
11.	Есть три кучки камней. За ход можно брать любое количество камней из какой-либо одной кучки. Тот, кто не сможет сделать ход, считается выигравшим. Найдите все выигрышные позиции.