Обозначим через g(n) число, характеризующее позицию с одной кучкой из n орехов: это наименьшее неотрицательное число, которое не получается как исключающее ИЛИ значений для кучек после одного хода.

Кучку из 1 ореха разделить нельзя, поэтому g(1) = 0.
Для 2 орехов единственный ход — разделить кучку на 1 и 1. Получаем g(2) = 1.
Для 3 орехов единственный вариант — 1 и 2, поэтому g(3) = 0.
Кучку из 4 орехов можно разделить на 1 и 3 или на 2 и 2. В обоих случаях исключающее ИЛИ значений равно 0, значит g(4) = 1.
Кучку из 5 орехов можно разделить на 1 и 4 или на 2 и 3. В обоих случаях исключающее ИЛИ равно 1, поэтому g(5) = 0.
Для пяти кучек из 5 орехов исключающее ИЛИ равно 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0. Это проигрышная позиция для того, кто ходит первым: после любого его хода соперник может вернуть позицию с исключающим ИЛИ 0.

Ответ: мистеру Фоксу следует играть за второго игрока.

Поделись с друзьями