2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Сложная задача
Сообщение03.12.2010, 21:31 

(Оффтоп)

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

 
 
 
 Re: Сложная задача
Сообщение03.12.2010, 22:08 
Эту задачу сформулировал Вишенский В.А, г. Киев.

 
 
 
 Re: Сложная задача
Сообщение03.12.2010, 22:27 
Кто выиграет при $n=3m+2$?

 
 
 
 Re: Сложная задача
Сообщение04.12.2010, 15:42 

(2 romanz)

romanz в сообщении #383281 писал(а):
Эту задачу сформулировал Вишенский В.А, г. Киев.
Я хотел сказать, что можно было бы убрать лишние разрывы строк и переносы. Выглядит ужасно.

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

 
 
 
 Re: Сложная задача
Сообщение04.12.2010, 16:19 
Аватара пользователя
Похоже на Grundy's game.
Скорее всего, также сводится к ниму.

 
 
 
 Re: Сложная задача
Сообщение04.12.2010, 18:51 
Возможно, но я не знаю как ее решить, даже при $m=2$.

 
 
 
 Re: Сложная задача
Сообщение06.12.2010, 08:45 
При $m=2$ совсем легко. Выигрыш совсем не зависит от действий игроков. Результат определен четностью $n$.

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

 
 
 
 Re: Сложная задача
Сообщение06.12.2010, 17:42 
Аватара пользователя
Используйте функцию Шпрага-Гранди.

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

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

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group