Крестики-крестики

[fiviol]

Двое игроков по очереди ставят крестики на клетчатом поле размера $n$ на 1. Выигрывает тот, после чьего хода на поле окажется 3 крестика подряд.
При каких $n$ выигрывает второй игрок?

[waxtep]

При $n=6m$ второй выигрывает, но, это, наверное, не всё...

[fiviol]

Не только не все, но и не верно. :) Например, при 18 второй проигрывает.

[Gagarin1968]

Сорри за некропостинг, но только сейчас обратил внимание на эту тему 6-летней давности. Как я понимаю, fiviol так и не выложил решение.

Я написал небольшую программку, и получилось вот что: при $n=6\left\lfloor{\dfrac {3m-1}{2}}\right\rfloor,~m\in\mathbb{N}$ выигрывает второй, иначе — первый.

То есть второй выигрывает, если сомножитель при шестёрке не кратен $3$, иначе говоря если длина полосы равна $6, 12, 24, 30, 42, 48, 60,\ldots$ клеток.
Правда, полной уверенности в правильном ответе у меня нет, т.к. программист я очень слабый.
fiviol, это правильный ответ?

[fiviol]

Я не помню, знаю ли я ответ. :) Надо будет порешать.

[Gagarin1968]

fiviol в сообщении #1666285 писал(а):

Я не помню, знаю ли я ответ.

Хорошие дела!
А 6 лет назад знали?

[fiviol]

Порылся в своих архивах - нет, я решения не знаю, но ответ $6, 12, 24, 30, 42, 48, 60,\ldots$ не верен.
У меня имеется вычисленная на компьютере (не мною) последовательность выигрышных для второго игрока значений $n$ в пределах 10000:
$6, 12, 22, 30, 32, 44, 54, 64, 76, 86, 98, 110, 118, 130, 132, 162, 170, 184, 194, 202, 282, 290, 302, 356, $$1046, 2502, 2752, 2912, 3052, 3076, 7250, 7356, 7866$
(не знаю, есть ли такая на сайте целочисленных последовательностей),
и моё утверждение о том, что у меня при ручных вычислениях в пределах 30 получился тот же набор значений.

-- 20.12.2024, 17:36 --

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

[Gagarin1968]

fiviol в сообщении #1666290 писал(а):

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

Было бы любопытно взглянуть.

[fiviol]

Вот тут в комментариях можно почитать:
https://fiviol.livejournal.com/59263.html

[waxtep]

Интересная задача, увлекся шесть лет спустя повторно, правда, не могу похвастаться тем, что решил. В OEIS такой последовательности нет. Поскольку поставить крестик рядом с уже поставленным, или через один, - означает проиграть, каждый поставленный крестик "запрещает" от $3$ до $5$ клеток. Буду в дальнейшем обозначать подобное как $3\div5$.
Задачу можно сформулировать так: дано мультимножество натуральных чисел $A=\{a_i\}$; за один свой ход (полуход) игрок может и должен сделать одно из следующего:
- убрать одно любое $a_i\leqslant5$
- уменьшить одно любое $a_i\geqslant4$ на $3\div5$ так, чтобы результат был положительным
- убрать одно любое $a_i\geqslant7$ и добавить два натуральных числа $x, a_i-x-5$
Исходно $A=\{n\}$, выигрывает тот, после чьего хода$A=\varnothing$
Теперь, начнем с конца и увидим, что второй игрок форсированно выигрывает ровно за два полухода при $A=\{6\}$ или $A=\{1\div3,1\div3\}$. Двигаясь назад, найдем варианты, форсированно выигрываемые вторым ровно за четыре полухода при его оптимальной игре:

$$A=\begin{cases}\{12\}\\ \{6,6\};\{1\div3,9\div11\}\\ \{1\div3,1\div3,6\}\\ \{1\div3,1\div3,1\div3,1\div3\}\end{cases}$$

И есть еще одна неприятная вариация, когда второй выигрывает за два полухода или за четыре, в зависимости от поведения первого, это $A=\{4\div5,4\div5\}$. Такие вариации, зависящие от поведения первого игрока, будут всегда, поскольку в целом "извести" какое-то $n$ можно за $\lceil{n/5}\rceil\div{\lceil{n/3}\rceil}$ полуходов. Для написания внятного алгоритма осталось четко сформулировать закономерность, по к-рой варианты двигаются "назад", этого у меня пока нет. Я, кхм, формально пишу, например, $12=1\div3\oplus9\div11$, но как именно работает это $\oplus$ - не допер

[Null]

waxtep в сообщении #1667877 писал(а):

но как именно работает это $\oplus$ - не допер

Функция Шпрага-Гранди и двоичный XOR

[waxtep]

Null так просто, в самом деле? xor из индикаторов выигрыша для возможных вариантов после полухода. При этом можно сразу убирать симметричные варианты, они по-любому друг с другом поксорятся в ноль. Можно будет на досуге запрогать, а перед этим желательно ещё и подумать. Спасибо и с наступающим!

-- 31.12.2024, 15:08 --

waxtep в сообщении #1667955 писал(а):

xor из индикаторов выигрыша для возможных вариантов после полухода

А нет, посложнее, в общем, следует вдуматься

[waxtep]

Да, похоже, эта шайтан-машина работает! Мне хватило усидчивости дойти на бумажке до $n=32$. Действительно, не разбираясь детально в теории (это не успел), выглядит как магия: все разнообразие вариантов прячется в xor между "уровнями новизны" для постановки крестика вдали от краёв поля

[fiviol]

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

[waxtep]

fiviol в сообщении #1668278 писал(а):

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

Не могу похвастаться, что разобрался, поскольку предложенная уважаемым Null общая теория явилась для меня deus ex machina. И она же убивает любую игру, где двое ходят одинаковыми крестиками! Расставил аккуратно конечные позиции и пошёл ксорить направо и налево. Нужен какой-то новый поворот сюжета, отменяющий этого Герцшпрунга-Рассела Шпрага-Гранди