Проблема 301: Его
Ним - игра, играемая с кучами камней, где два игрока берут ее в свою очередь, чтобы удалить любое количество камней из любой кучи, пока камни не останутся.
Мы рассмотрим версию Nim с нормальной загрузкой с тремя кучками, которая работает следующим образом:
В начале игры есть три кучи камней.
В свою очередь игрок удаляет любое положительное количество камней из одной кучи.
Первый игрок, который не может двигаться (потому что камни остаются), теряет.
Если (n1, n2, n3) указывает позицию Nim, состоящую из кучек размера n1, n2 и n3, тогда существует простая функция X (n1, n2, n3) - которую вы можете искать или пытаться вывести для себя - это возвращает: ноль, если с совершенной стратегией игрок, который собирается двигаться, в конечном счете проиграет; или ненулевое, если с идеальной стратегией игрок, который собирается двигаться, в конечном счете победит. Например, X (1,2,3) = 0, потому что, независимо от того, что делает текущий игрок, его оппонент может ответить движением, которое уходит две кучи одинакового размера, после чего каждый ход текущего игрока может быть отражен его противником до тех пор, пока не останутся камни; поэтому текущий проигрыватель проигрывает. Проиллюстрировать:
текущий игрок переходит в (1,2,1)
противник переходит к (1,0,1)
текущий игрок переходит в (0,0,1)
противник переходит к (0,0,0), и поэтому выигрывает.
Для скольких положительных целых чисел n ≤ 230 X (n, 2n, 3n) = 0?