Сложная задача (игра с разложением в сумму)

[romanz]

Задано число $m > 1$ и сумма нескольких натуральных слага-
емых. Двое игроков играют в игру: за каждым ходом необходимо одно
из слагаемых, которое большее $m$, разложить в сумму двух меньших.
Ходят игроки поочередно и проигрывает тот игрок, который не мо-
жет исполнить очередной ход (т.е. когда каждое слагаемое не превы-
шает $m$). Выиграет ли при правильной игре обеих игроков тот, кто
начинает, если игра начинается с единого слагаемого $n$?

[arseniiv]

(Оффтоп)

И откуда вы это скопировали?

[romanz]

Эту задачу сформулировал Вишенский В.А, г. Киев.

[Null]

Кто выиграет при $n=3m+2$?

[arseniiv]

(2 romanz)

romanz в сообщении #383281 писал(а):

Эту задачу сформулировал Вишенский В.А, г. Киев.

Я хотел сказать, что можно было бы убрать лишние разрывы строк и переносы. Выглядит ужасно.

А сейчас уже поздно.

[maxal]

Похоже на Grundy's game.
Скорее всего, также сводится к ниму.

[romanz]

Возможно, но я не знаю как ее решить, даже при $m=2$.

[Cash]

При $m=2$ совсем легко. Выигрыш совсем не зависит от действий игроков. Результат определен четностью $n$.

P.S. Прошу прощения, не заметил, что 2 уже нельзя раскладывать...

[maxal]

Используйте функцию Шпрага-Гранди.

[romanz]

Да, действительно, решение можно получить, но уже при $m=2$ и $n=15$ вручную надо проделать большой объем работы. При больших значениях $m$ объем вычислений быстро растет. Нужна программа.

О функции Шпрага-Гранди впервые слышу от Вас. Весьма благодарен за советы.