Во-первых, данное решение неверно. Вы заметили, что он не использует k, и действительно, это большой красный флаг. Вы также можете посмотреть на результат, который он дает для игры с одной стопкой, где кажется, что игрок А выигрывает только в том случае, если размер стопки равен тому, который вы должны довольно быстро показать, неверно.
Структура ответа вроде бы правильная. Большая часть числа Гранди состоит в том, что число Гранди в комбинированном игровом состоянии представляет собой сумму nim (XOR в случае конечных ординалов) чисел Гранди для отдельных игровых состояний. (Это работает только для очень специфического способа объединения игровых состояний, но это оказывается естественным способом рассмотрения куч Nim.) Таким образом, эту проблему действительно можно решить, найдя число Гранди для каждой стопки (учитывая k) и XOR-их вместе, чтобы получить номер Гранди для полного игрового состояния. (В Nim, где вы можете взять любое количество камней из кучи и выиграть, взяв последний камень, число Грунди в куче равно размеру кучи. Вот почему решение этой версии Nim состоит в том, что XOR размеры свай.)
Таким образом, принимая теорию как должное, вы можете решить проблему, найдя правильные значения Гранди для одной кучи с учетом k. Вам нужно только рассмотреть одну кучу игр, чтобы сделать это. На самом деле это довольно классическая проблема, и IMO значительно проще правильно анализировать, чем Nim с несколькими кучами. Вы должны попробовать.
Что касается того, как думать о числах Гранди, есть много мест, чтобы прочитать об этом, но вот мой подход. Необходимо понять, почему комбинация двух игровых состояний позволяет предыдущему игроку (B) выигрывать именно тогда, когда числа Гранди равны.
Чтобы сделать это, нам нужно только рассмотреть, какое влияние оказывают движения на числа Гранди двух состояний.
По определению в качестве минимального исключенного значения состояний-преемников всегда существует ход, который изменяет число Гранди состояния на любое более низкое значение (т. Е. n может стать любым числом от 0 до n - 1) , Ни один ход не оставляет число Гранди неизменным. Могут быть или не быть ходы, которые увеличивают число Гранди.
Затем, в случае комбинации двух состояний с одним и тем же номером Гранди, игрок B может выиграть, используя «стратегию подражания». Если игрок A делает ход, который уменьшает число Гранди одного состояния, игрок B может «копировать», уменьшая число Гранди другого состояния до того же значения. Если игрок A делает ход, который увеличивает число Гранди одного состояния, игрок B может «отменить» его, делая ход в том же состоянии, чтобы уменьшить его до того же значения, что было раньше. (Наша игра конечна, поэтому нам не нужно беспокоиться о бесконечном цикле действий и отмены.) Это единственное, что может сделать A. (Помните, что важно то, что ни один ход не оставляет число Гранди без изменений.)
Если у штатов не одно и то же число Гранди, тогда путь для первого игрока очевиден; они просто уменьшают номер состояния с более высоким значением, чтобы сопоставить состояние с более низким значением. Это сводит вещи к предыдущему сценарию.
Здесь следует отметить, что определение минимального исключенного значения позволяет нам построить число Гранди для любых состояний рекурсивно с точки зрения их преемников (по крайней мере, для конечной игры). Выборов нет, поэтому эти цифры на самом деле четко определены.
Следующий вопрос, который следует рассмотреть, - почему мы можем вычислить число Гранди для комбинированного состояния. Я предпочитаю вообще не думать о XOR. Мы можем определить эту операцию nim sum исключительно из свойства минимального исключенного значения. Мы абстрактно считаем преемников nim_sum(x, y) равными {nim_sum(k, y) for k in 0..x-1} и {nim_sum(x, k) for k in 0..y-1}; другими словами, переход на одно подсостояние или другое. (Мы можем игнорировать преемника одного из подсостояний, которые увеличивают число Гранди, поскольку в таком состоянии все преемники исходного состояния будут иметь плюс nim_sum(x, y) в качестве другого преемника, поэтому оно должно иметь строго большее число Гранди Да, это немного волнисто.) Это похоже на XOR. У меня нет особенно приятного объяснения этому, но я чувствую, что нет необходимости в базовом понимании. Важно то, что это четко определенная операция.