Игра Гранди

[General]

Существует такая математическая игра:

Лежит кучка из N спичек, скажем, N=24. Два игрока по очереди могут делить кучку на 2 неравные. К примеру, первым ходом из 24 можно получить 4 и 20. Следующий игрок может разбить или 4 на 1+3, или 20 на всё, что у годно, кроме 10+10. В итоге получится 3 кучки спичек.

Выигрывает тот, после чьего хода останутся только пары и одиночные спички. Вот пример партии:
на старте было 14
1: 3+11
2: 1+2+11
1: 1+2+3+8
2: 1+2+3+3+5
1: 1+2+3+3+1+4
2: 1+2+1+2+3+1+4
1: 1+2+1+2+3+1+1+3
2: 1+2+1+2+1+2+1+1+3
1: 1+2+1+2+1+2+1+1+1+2 и выиграл.

Вопрос: при каких стартовых количествах спичек выигрывает первый игрок, а при каких - второй, при условии, что оба играют безошибочно.

[T2Ton]

в 4й строке примера ошибка

а вообще интересно.. надо подумать..

[Dimon157]

Скрытый текст

#спичек - игрок-победитель
3-1
4-2
5-1 (1+4)
6-1 (2+4)
7-2
8-1 (1+7)
9-1 (2+7)
10-2 (4+6, 2+4+4)
11-1 (1+10)
12-1 (1+10)
Вроде бы закономерность видна, но как доказать строго...

Прикольно в примере второй игрок засунул 2 спички в рукав, но даже это его не спасло

[General]

Tushcan
Спасибо, поправил, решил начать с 14, чтобы вперёд не переделывать строки

Dimon_157

Скрытый текст

Ну а для 13 кто победит?

[Dimon157]

Скрытый текст

13-2
14-1
15-1
Еще более уверился в закономерности

[General]

Dimon_157

Скрытый текст

А если из 13-ти первый сделает ход 5+8?

[Dimon157]

Скрытый текст

1: 5+8
2: 2+3+8
1: 2+(2+1)+8 - выигрыш ходящего, то есть второго

[General]

Скрытый текст

Собственно, давай получающиеся двойки и единицы просто опускать
1: 5+8
2: 3+8
1: 3+6

Тогда
а)
2: 3+5
1: 3+3 и выигрыш 1го

б)
2:3+4
1:3+3 и выигрыш 1го

в)
2: 6 и затем прооигрывает.

Так что начав из 13ти спичек, выигрывает первый.

[Dimon157]

Скрытый текст

Да, Генерал, верно.
Не удержался и залез на википедию.
Там говорится что ф-ция гранди обладает свойством
F(G1, G2) = F(G1) xor F(G2).
Проверил на данных в этой задаче - работает!

Сюда заглядывать только Генералу

Скрытый текст

<div class='quotetop'>Цитата</div>

Although these values have been calculated to around n = 2^35, this sequence is still not completely understood. It is possible that the sequence will eventually become periodic, although this has not been seen to happen yet.[/b]

За простой формулировкой оказалось далеко не банальное решение.

[General]

Скрытый текст

<div class='quotetop'>Цитата</div>

За простой формулировкой оказалось далеко не банальное решение.[/b]

Извини, всё забывал отписаться - да-да, мне кгда преподаватель эту задачку загадывал, я крутил её, крутил, но потом-таки в нете нашёл решение.