Задача
COM-B1-M08-P024 Кучи \(7,11,13\)
Есть три кучи: \(7\), \(11\) и \(13\) камней. За ход можно взять любое положительное число камней из одной кучи. Последний ход выигрывает. Найдите выигрышный первый ход и докажите, что он действительно выигрышный.
Вычислите \(7\oplus11\oplus13\).
В двоичной записи \(7=0111\), \(11=1011\), \(13=1101\). Ним-сумма равна \(0111\oplus1011\oplus1101=0001\). Нужно уменьшить одну кучу так, чтобы ним-сумма стала \(0\). Например, уменьшим \(13\) до \(12\), потому что \(7\oplus11\oplus12=0\). После этого, если соперник изменит одну кучу, ним-сумма станет ненулевой. В куче, где стоит старший единичный бит этой суммы, можно уменьшить число так, чтобы общая ним-сумма снова стала \(0\). Повторяя это, первый игрок каждый раз возвращает сопернику нулевую ним-сумму и в конце берет последний камень.
Задача сильная для книги 1, но полезна как мост к более продвинутой комбинаторике.