Игра с числом 11111111122222222333333344444455555

[Ktina]

На доске написано число 11111111122222222333333344444455555.

Ярдена и Шуламит играют в такую игру:

За один ход разрешается стереть любое количество одинаковых цифр (разумеется, ненулевое). Выигрывает та из девочек, которая сотрёт последнюю цифру. Ярдена ходит первой.

Кто выигрывает при правильной игре обеих сторон? Как нужно для этого играть?

[mustitz]

Ним?

[Ktina]

mustitz
Ним-то Ним, однако, существует ли крависое частное решение?

[pcyanide]

Главную роль в стратегии играет операция Исключающее ИЛИ (англ Exclusive или XOR) обозначаемая на языке C (и производных от него) знаком ^(carpet). Результат операции для одинаковых двоичных разрядов (0 или 1) равен 0, а для разных разрядов равен 1: 0^0 = 1^1 = 0,   0^1 = 1^0 = 1

Попытаюсь перевести стратегию игры (из Википедии) с языка XOR на русский.

В начальной позиции (если я не ошибся подсчетом) у нас 9 единиц, 8 двоек, 7 троек, 6 четверок и 5 пятерок.

Переводим числа в двоичную систему счисления и записываем друг под другом. Затем под каждым разрядом записываем 0, если количество единиц в этом разряде четно и 1, если количество единиц нечетно. Полученное число (т.е. XOR всех количеств) будем называть ним-суммой:

$$ \begin{matrix} \text{№ кучи} & \text{Содержимое} & \text{К-во(десят.)} & \text{К-во(двоич.)} \\ 1 & \text{Единицы} & 9 & 1001 \\ 2 & \text{Двойки} & 8 & 1000 \\ 3 & \text{Тройки} & 7 & 0111 \\ 4 & \text{Четверки} & 6 & 0110 \\ 5 & \text{Пятерки} & 5 & 0101 \\ & \text{——————} & & \text{———} \\ & \text{Ним-сумма} & & 0101 \end{matrix} $$

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

Если ним-сумма ненулевая, надо ее сделать нулевой в результате своего хода. Для этого отмечаем самый старший разряд (крайний слева) ним-суммы, содержащий единицу, и ищем кучу, количество которой также содержит единицу в отмеченном разряде. (Такая куча найдется, так как количество куч с единицей в отмеченном разряде нечетно.) В количестве этой кучи надо поменять на противоположный каждый разряд, в котором ним-сумма содержит единицу. (Другими словами "XOR-им" количество кучи с ним-суммой) Так как отмеченный разряд изначально содержит 1, то он станет нулевым, следовательно количество уменьшится. Вычитаем новое количество из старого и получаем количество предметов, которое следует взять из выбранной кучи в качестве очередного хода (в данном случае это количество стираемых цифр).

В нашем (начальном) случае ним-сумма равна 0101. Единицу в 3-м разряде (разряды нумеруются справа налево) содержат количества куч 3, 4 и 5. Берем какую-то из них. Куча 5 содержит в точности 0101, следовательно ее можно просто опорожнить (стереть все пятерки). Рассмотрим менее тривиальный случай, например кучу 4. Она содержит 0110 или 6 десятичное. Поменяв на противоположные разряды 1 и 3 (именно в этих разрядах ним-сумма содержит единицу), получим 0011 или 3 десятичное. Следовательно надо выбрать 6-3 = 3 предмета из 4-й кучи (стереть 3 четверки). В результате получим:

$$ \begin{matrix} \text{№ кучи} & \text{Содержимое} & \text{К-во(десят.)} & \text{К-во(двоич.)} \\ 1 & \text{Единицы} & 9 & 1001 \\ 2 & \text{Двойки} & 8 & 1000 \\ 3 & \text{Тройки} & 7 & 0111 \\ 4 & \text{Четверки} & 3 & 0011 \\ 5 & \text{Пятерки} & 5 & 0101 \\ & \text{——————} & & \text{———} \\ & \text{Ним-сумма} & & 0000 \end{matrix} $$

оставляя соперника без выигрышной стратегии.

[Ktina]

pcyanide
Большое спасибо!