Задача 60915

Темы:    [ Ним-сумма ] [ Выигрышные и проигрышные позиции ]

Сложность: 4+ Классы: 8,9,10,11 Название задачи: Игра "Ним".

Условие

Игра ``Ним''. Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять любое (ненулевое) количество камней, но только из одной кучки. Выигрывает тот, кто взял последний камень. Для анализа игры каждому набору кучек камней m<sub>1</sub>, m<sub>2</sub>, ..., m<sub>l</sub> поставим в соответствие его ним сумму (5.1 ).
а) Докажите, что если игрок делает ход из позиции с нулевой ним-суммой, то в результате получается позиция с ним-суммой n 0.
б) Докажите, что из позиции с ненулевой ним-суммой всегда можно сделать ход в позицию с ним-суммой n = 0.
в) Опишите выигрышную стратегию в игру ``Ним''.
г) Какой следует сделать ход, если перед вами три кучки: 3, 4 и 5 камней?

Решение

а) Если n равнялось 0 и одно из чисел m₁, m₂, ..., m_l изменилось, то изменится и число n. Оно станет равно количеству взятых камней, отличному от нуля.
б) Согласно задаче 5.76 г), для некоторого j ( 1 j l) выполняется неравенство m_j n < m_j. Поэтому из j-ой кучки можно взять m_j - (m_j n) камней, что приведет к обнулению ним-суммы.
в) Игрок находится в проигрышной позиции, если перед его ходом n = 0. Все остальные позиции — выигрышные. Для того, чтобы выиграть в ``Ним'', нужно оставлять после своего хода проигрышную позицию.
г) Сделайте переход к позиции 1, 4, 5.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	5
Название	Числа, дроби, системы счисления
Тема	Системы счисления
параграф
Номер	3
Название	Двоичная и троичная системы счисления
Тема	Двоичная система счисления
задача
Номер	05.077