Задача 301
Ним

Ним - это игра с кучками камней, в которой двое игроков по очереди убирают любое количество камней из любой кучки, пока не останется ни одного камня.

Мы рассмотрим версию нормальной игры с тремя кучками, которая проходит следующим образом:
- в начале игры имеется три кучки камней;
- во время своего хода игрок убирает любое положительное число камней из любой одной кучки;
- первый игрок, который не сможет сделать ход (потому что не останется камней), проигрывает.

Если (n_(1),n_(2),n_(3)) указывает позицию в игре с кучками размеров n_(1), n_(2) и n_(3), то существует простая функция X(n_(1),n_(2),n_(3)) (которую вы можете разыскать или попытаться вывести самостоятельно), которая возвращает:

  • ноль, если при совершенной стратегии игрок, чья очередь делать ход, в конце концов проиграет; или
  • ненулевой результат, если при совершенной стратегии игрок, чья очередь делать ход, в конце концов выиграет.

Например, X(1,2,3) = 0, потому что, независимо от действий текущего игрока, его противник может ответить ходом, который оставит кучки равных размеров, и тогда каждый ход текущего игрока может повторяться его противником, пока не останется камней - то есть, текущий игрок проигрывает. Для иллюстрации:
- текущий игрок ходит в позицию (1,2,1),
- противник ходит в (1,0,1),
- текущий игрок ходит в (0,0,1),
- противник ходит в (0,0,0) и выигрывает.

Для скольки положительных целых n ≤ 2^(30) выполняется X(n,2n,3n) = 0 ?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net