Игра с АСМ-олимпиады

[Sonic86]

Дана пустая лента из $n$ ячеек. Два игрока по очереди ставят в пустые ячейки крестики. Проигрывает тот, кто на очередном ходе не сможет не поставить крестик в ячейку рядом с уже заполненной ячейкой. При каких $n$ при правильной игре выигрывает первый (ну или второй).
Решения я не знаю.

(предыстория)

Лет 6 назад давали. Иногда на таких олимпиадах дают одну-две задачи, которые можно решить не составлением программы, а решить как задачи.. Правда почему-то жюри на такие решения смотрят как на непрофессиональные...
Эту задачу я решить тогда не смог.

[Null]

Как-то непонятно. Уже первый ход сделать нельзя.

[Sonic86]

Почему? Первый ход всегда сделать можно.
Обозначу ленту с крестиками вектором $(0;0;0;0;0)$.
Примеры игры:
1. А: $(0;0;1;0;0)$
В: $(0;0;1;0;1)$
А: $(1;0;1;0;1)$
В: проиграл.

2. А: $(0;1;0;0;0)$
В: $(0;1;0;1;0)$
А: проиграл.

[Руст]

Если я правильно понял, то Игрок может ставить крестик рядом с заполненной клеткой, если при этом у него есть возможность ставить крестик на клетке, не являющейся соседнем с заполненной ранее. Если такой возможности уже нет, то он проиграл.

[Sonic86]

Ой! Давайте проще скажу: кто поставил крестик рядом с заполненной клеткой, тот и проиграл

[Руст]

Так бы сразу написали. Иначе первое ваше условие скорее трактуется как я писал.

[Sonic86]

Прошу прощенья могу исправить

[lim0n]

А если условие переформулировать, ведь после того, как поставили крестик, его и соседние с ним клетки можно вырезать из ленты...

В начале игры на столе есть одна кучка с $n$ предметами. Игрок на своём ходе выбирает кучку, берет из неё не более трёх предметов, а оставшиеся в ней предметы делит на две кучки. Выигрывает тот, кто взял последний предмет со стола.

[Null]

При нечетном n первый выигрывает поставив в середину а потом по симметрии.

[Руст]

При четном $n>2$ выигрывает второй, отвечая ходу первого на $i$ ходом $i\pm \frac n2$, так же по симметрии.

[Sonic86]

Руст писал(а):

При четном $n>2$ выигрывает второй, отвечая ходу первого на $i$ ходом $i\pm \frac n2$, так же по симметрии.

1: $(0;0;1;0;0;0)$
2: $(0;0;1;0;0;1)$
1: $(1;0;1;0;0;1)$
2: $(1;0;1;1;0;1)$ - проиграл.
Или я неверно понял Ваш ответ?

[MrDindows]

При n=2 побеждает первый.
При n=4 второй.
При n=6 первый (ставит крестик в крайнюю клетку, сводя ситуацию к случаю n=4, где он уже будет вторым)
При n=8 первый (крест в четвёртую клетку)

[staric]

MrDindows в сообщении #430400 писал(а):

При n=8 первый (крест в четвёртую клетку)

А второй - в восьмую?

[Equinoxe]

Да, 8-ая прогрышная. Вообще, если верить моей программе, то среди первых двухсот n проигрышные:
4, 8, 14, 20, 24, 28, 34, 38, 42, 54, 58, 62, 72, 76, 88, 92, 96, 106, 110, 122, 126, 130, 140, 144, 156, 160, 164, 174, 178, 190, 194, 198
А закономерность такова (по крайней мере на первых 20000): если рассматривать, насколько отличаются соседние плохие n,
то получится последовательность с предпериодом «4 4 6 6 4 4 6 4 4» и периодом «12 4 4 10 4».
Осталось лишь доказать эту закономерность по индукции.