Игра 5: Мариенбад

На столе четыре кучки фишек. В кучках лежат 1, 3, 5 и 7 фишек. На каждом ходу игрок берет любое число фишек из выбранной кучки (минимум одну фишку, максимум все). Выигрывает тот, кто забирает последнюю фишку. Для какого игрока существует выигрышная стратегия?

Аналогично предыдущему случаю получим:

1 в двоичной системе: 1

3 в двоичной системе: 11

5 в двоичной системе: 101

7 в двоичной системе: 111

Так как в начальной позиции суммы цифр в каждом столбце четные, первый игрок не может выиграть. Выигрышная стратегия существует для второго игрока. Любой ход первого игрока сделает сумму цифр хотя бы в одном столбце нечетной. Допустим, что первый игрок взял одну фишку из кучки с тремя фишками. Получим:

1 в двоичной системе: 1

2 в двоичной системе: 10

5 в двоичной системе: 101

7 в двоичной системе: 111

NIMROD

В начале 50-х годов XX века инженеры английской компании Ferranti создали первый компьютер, предназначенный только для игр. Он назывался NIMROD. Первые три буквы NIM означали игру, для которой он и был спроектирован. На панели компьютера находились светящиеся лампочки, которые представляли положение фишек в игре. Прототип компьютера был представлен на выставке «Фестиваль Британии» в 1951 году. Считается, что это послужило началом эпохи электронных игр.

Теперь второй игрок должен сделать такой ход, чтобы сумма цифр в правом столбце стала четной, а остальные не изменились, так как они уже четные. Значит, нужно взять одну фишку из любой кучки, кроме второй. В двоичной системе это означает, что нужно заменить 1 на 0 в правом столбце.

Хотя найти стратегию игры Ним было намного сложнее, чем для предыдущих игр, о которых мы рассказали, для всех этих игр справедлива одна общая идея. Нужно найти равновесную ситуацию, которая совпадает с конечным положением, и определить, какой из игроков всегда сможет сохранять подобную ситуацию, а какой — никогда. Так, в первой игре этой главы («Игра 1: выигрывает первый») равновесная ситуация такова: нужно оставить на столе число фишек, кратное 3. Во второй игре («Игра 2: выигрывает второй») нужно записать число, кратное 11, а в последней игре Ним нужно оставить в каждой кучке такое число фишек, чтобы при записи количества фишек в двоичной системе сумма цифр в столбцах всегда была четной.

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

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

ДВОИЧНАЯ СИСТЕМА СЧИСЛЕНИЯ

Это позиционная система счисления, в которой любое число можно представить с помощью всего двух цифр: 0 и 1. Чтобы преобразовать двоичное число в десятичное, нужно заменить все единицы степенями двойки. Показатели этих степеней будут зависеть от позиции цифры: правый разряд соответствует 2⁰, следующий — 2¹ и так далее. Например, двоичное число 110101 в десятичной системе выглядит так: 1 • 2⁰ + 0 • 2¹ + 1 • 2² + 0 • 2³ + 1 • 2⁴ + 1 • 2⁵ = 1 + 4 + 16 + 32 = 53.

Аналогично для записи десятичного числа в двоичном виде нужно разделить его на 2, полученный результат снова разделить на 2 и так далее до тех пор, пока результатом деления не будет 1. Последний результат деления будет первой цифрой справа. Все прочие остатки отделения, от последнего к первому, составят следующие разряды (остаток от деления на 2 может равняться только 0 или 1). Например, 39 в двоичной системе записывается как 100111, так как 39:2 дает 19 (и остаток 1), 19:2 дает 9 (остаток 1), 9:2 дает 4 (остаток 1), 4:2 дает 2 (остаток 0), 2:2 дает 1 (остаток 0). Мы выразили число в виде суммы степеней двойки.

Итак, 39 =1 + 2 + 4 + 32 = 1•2⁰ +1•2¹+1•2²+0•2³+0•2⁴+1•2⁵ = 100111 по основанию 2. Хотя двоичная нотация появилась сравнительно недавно, свойство, на котором она основана («всякое число можно представить в виде суммы различных степеней двойки»), было известно и применялось еще в древности. Например, древние египтяне использовали для умножения такую систему. Один из сомножителей удваивался, второй делился на 2. Если число было нечетным, то на 2 делилось предыдущее число. Этот метод дает верный результат именно благодаря указанному свойству.

Страница бюллетеня Французской академии наук, посвященная двоичной системе счисления, разработанной Лейбницем в 1703 году.

НЕСКОЛЬКО ИНТЕРЕСНЫХ ИГР

Вращаем кубик. Это стратегическая игра для двух игроков. Первый игрок ставит кубик на стол выбранной стороной вверх. Второй игрок поворачивает кубик на четверть оборота так, что на верхней грани будет уже другое число очков, и прибавляет это число к первому. Затем каждый игрок по очереди вращает кубик на четверть оборота (так можно получить любое число, кроме тех, что расположены на верхней или нижней грани кубика) и прибавляет число очков на верхней грани к общей сумме. Тот, кто набирает в сумме 31, выигрывает.

Какой из игроков имеет преимущество? Как нужно играть, чтобы всегда выигрывать?

Разрезаем прямоугольник. Это стратегическая игра для двух игроков. На листе бумаги в клетку нужно нарисовать прямоугольник размерами 17 ? 15 клеток. Затем нужно пометить квадратик в нижнем правом углу. Каждый из игроков своим ходом делит прямоугольник на две части вертикальной или горизонтальной линией и удаляет ту часть прямоугольника, которая не содержит маленький отмеченный квадрат. Тот, кто не сможет разделить прямоугольник (то есть от прямоугольника останется только один отмеченный квадратик), проигрывает.

Какой из игроков имеет преимущество? Как нужно играть, чтобы всегда выигрывать?

Пересекаем круг. Это стратегическая игра для двух игроков. На листе бумаги нужно нарисовать окружность и обозначить на ней восемь произвольных точек. На каждом ходу игрок соединяет две точки отрезком. Он может соединить любые две точки, кроме уже соединенных, но нарисованный им отрезок не должен пересекать никакой другой отрезок. Игрок, которому не удастся провести такой отрезок, проигрывает.

Какой из игроков имеет преимущество? Что изменится, если изменить начальное число точек?