Задача
Игра Ним''.</b>Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять любое (ненулевое) количество камней, но только из одной кучки. Выигрывает тот, кто взял последний камень. Для анализа игры каждому набору кучек камней<i>m</i><sub>1</sub>,<i>m</i><sub>2</sub>, ...,<i>m</i><sub>l</sub>поставим в соответствие его ним сумму (<a href="https://mirolimp.ru/tasks/160914">5.1</a>). а) Докажите, что если игрок делает ход из позиции с нулевой ним-суммой, то в результате получается позиция с ним-суммой<i>n</i>$\ne$0. б) Докажите, что из позиции с ненулевой ним-суммой всегда можно сделать ход в позицию с ним-суммой<i>n</i>= 0. в) Опишите выигрышную стратегию в игру Ним''.
г) Какой следует сделать ход, если перед вами три кучки: 3, 4
и 5 камней?
Решение
а) Еслиnравнялось 0 и одно из чиселm1,m2, ...,mlизменилось, то изменится и числоn. Оно станет равно количеству взятых камней, отличному от нуля. б)Согласно задаче 5.76г), для некоторогоj(1$\leqslant$j$\leqslant$l) выполняется неравенствоmj$\oplus$n<mj. Поэтому изj-ой кучки можно взятьmj- (mj$\oplus$n) камней, что приведет к обнулению ним-суммы. в) Игрок находится в проигрышной позиции, если перед его ходомn= 0. Все остальные позиции — выигрышные. Для того, чтобы выиграть в ``Ним'', нужно оставлять после своего хода проигрышную позицию. г) Сделайте переход к позиции 1, 4, 5.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь