Игра Ним

Не столь давно в салунах американского Среднего Запада можно было наблюдать любопытную игру. Начиналась она так. Бармен подзывал к себе подвыпившего ковбоя, выкладывал на стойку семь монет по одному доллару в две кучки - четыре и три доллара - и предлагал парню их выиграть: "Ставишь пять монет - получаешь двенадцать". Ковбой, отсчитав пять монет, клал их на стойку. Получалась третья кучка монет. Игра заключалась в том, что игроки по очереди берут монеты из этих кучек. Разрешается брать за один ход любое количество монет, но только из одной кучки. Забравший последнюю монету забирал и все остальные.

Источник - журнал "Квант".

На самом деле первоначальная позиция может быть не обязательно такой - 3, 4 и 5 монет, а любой, например, 10, 20 и 30 монет, а можно и увеличить количество кучек.

Выигрышная стратегия в этой игре связана с так называемой ним-суммой.

Для определения того выигрышная или проигрышная позиция у игрока надо:

1. Представить каждое из чисел в двоичной системе (например, исходная позиция 3, 9 и 13 монет. Тогда 3 в двоичной системе равно 2 + 1, 9 равно 8 + 1, а 13 равно 8 + 4 + 1).
2. Сложить слагаемые, встречающиеся нечетное количество раз, у нас это 2 + 1 + 4 = 7.
3.  Это и будет ним-сумма. 
4. Если эта сумма равна нулю, то позиция проигрышная.

Таким образом, оставляя после себя  позицию с ним-суммой равной нулю, мы обеспечим себе выйгрыш, ведь ним-сумма конечной позиции в игре (0 монет во всех кучках) равна нулю и появится она на столе после нашего хода.

Для примера рассмотрим какой ход нужно сделать при позиции 3, 9 и 13 монет.
3 = 0 + 0 + 2 + 1
9 = 8 + 0 + 0 + 1
13 = 8 + 4 + 0 + 1

Число 8 встречается четное число раз - его оставляем, число 4 встречается нечетное число раз, но в 1 кучке оно появиться не может, т.к. там мало монет, в кучке 2 тоже не может, т.к. тогда придется убрать 8 из первого ряда, остается убрать 4 монеты из 3 кучки, значит мы будем брать монеты из третьей кучки, но сколько? Забираем 4 монеты, в третьем столбце число 2 встречается нечетное число раз, значит из наших 4 монет положим 2 обратно, ну и в четвертом столбце три единицы - одну забираем. Итого мы должны забрать из 3 кучки 4 - 2 + 1 = 3 монеты. Получаем позицию:
3 = 0 + 0 + 2 + 1
9 = 8 + 0 + 0 + 1
10 = 8 + 0 + 2 + 0

Теперь вы можете самостоятельно рассчитать какой ход нужно сделать ковбою при позиции 3-4-5.

Похожие по тематике посты - еще почитать: