Задача

[yigal_s]

В куче 2009 камушков. За один ход можно взять один камень из любой кучи или разбить кучу на две.
Два игрока ходят по очереди.
Проигрывает тот, кто не может сделать ход.
Кто выиграет - первый или второй?

отсюда: http://matkruzhok.livejournal.com/8406.html?mode=reply

Что-то не решается...

Comments

[heller-i.livejournal.com]

Наверное можно решить динамикой + отложенными вычислениями.

Рекуррентное соотношение примерно такое:
Выиграет ли первый, для кучи с N камнями - P(1, N)

P(1, N) = !P(2, N-1) && !P(2, N-2) && !P(2, N-3) && .. && !P(2, N-(N-1))

По-моему, как-то так.

[yigal_s]

так задача вроде не на программирование, а на решение на бумаге

[cema.livejournal.com]

Решайте сзади. Т.е. случаи 1, 2, 3 камня. Потом гипотезу индукцией.

[yigal_s]

эхх, да ясно что не спереди.

случаи 1 2 3 рассмотрены, вот до гипотезы я не дошел пока

[zanuda.livejournal.com]

Ну для четного числа камней стратегия очевидна:
- первый первым ходом делит кучу на две равные части, а потом зеркалит ходы второго

Для нечетного числа камней нельзя первым ходом брать камень, а то задача сводится к предыдущей.

[zanuda.livejournal.com]

Кажется для любого нечетного числа камней большего одного первый проигрывает.

Он должен поделить кучу на две части. Пусть а и а+k. Где к - нечетное. При k=1 второй выравнивает кучи (делает a и а), а потом зеркалит. Отсюда следует, что при трех камнях первый проигрывает.

Если первый поделит кучи с k>=3, то второй делит вторую кучу на a и к. Получается три кучи - a,a и к. Ходы из первых двух куч тупо зеркалятся и ничего не меняют. Значит задача от 2a+k свелась к задаче для к. Ну и по индукции

[yigal_s]

похоже всё правильно.
и наверное, я б это не решил.

Спасибо. )))

[igogo3000.livejournal.com]

Есть более общее решение (для произвольной конфигурации кучек в начале игры):

Пусть n - общее количество камней, m - общее количество куч, k - количество куч, содержащих ровно один камень.

Проигрышная конфигурация - это конфигурация, при которой (n-m) четно и k четно.

Выигрышная конфигурация - любая другая, т.к. из нее одним ходом достигается проигрышная конфигурация.

Доказывается индукцией.

[yigal_s]

Очень интересно!

Спасибо.