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

[Null]

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

Расставил аккуратно конечные позиции и пошёл ксорить направо и налево.

Обычно нужно еще выявить закономерность, доказать ее и описать стратегию простыми словами. Например какой 1ый ход на полоске длинной 100?

[fiviol]

waxtep, я предлагаю всё-таки поразбирать игру в "4 крестика подряд", прежде чем говорить о её смерти.
Дело в том, что ксорить направо и налево теория Шпрага-Гранди предлагают для игр, которые разбиваются на сумму более простых игр (см. по той же ссылке). В игре "3 крестика подряд" такая конструкция возникает вполне естественно, а уже в игре "4 крестика подряд" её так запросто не построишь, если она вообще существует.

[waxtep]

Null в сообщении #1668400 писал(а):

Обычно нужно еще выявить закономерность, доказать ее и описать стратегию простыми словами. Например какой 1ый ход на полоске длинной 100?

Честно скажу, в эту сторону не пытался думать, кроме очевидной стратегии для нечетного $n$ - поставить первый крестик в середину. У меня сейчас не под рукой записи, по воспоминаниям, какой-то явной стратегии первого хода для четного $n$ не увидел (кроме общей теоретической рекомендации поставить крестик в клетку $x+3: F(x)=F(n-x-5)$, где $F$ - та самая магическая функция)

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

waxtep, я предлагаю всё-таки поразбирать игру в "4 крестика подряд", прежде чем говорить о её смерти.

Можно увидеть, что второй выигрывает при четном $n$: в этом случае ему доступна простая стратегия, - зеркалить ходы первого, пока тот не будет вынужден создать положение выигранное следующим ходом. Что касается нечетных $n$, хм. Тут я прочувствовал Ваш аргумент о разделении на независимые игровые поля уже на $n=5$: первый здесь выигрывает, поставив крестик в угол, а вовсе не в центр, как я в начале наивно подумал. Для $n=7$, наоборот, выигрывает постановка креста в центр; ну и видимо существуют какие-то нечётные $n$, когда выигрывает второй

-- 04.01.2025, 22:41 --

+ это мне как раз нравится, что тут (для четырёх крестов) с ходу общетеоретические Фраги-Краги с ходу не работают. Правда, и надежда получить результат вместе с этим становится более призрачной...

[Null]

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

тут (для четырёх крестов) с ходу общетеоретические Фраги-Краги с ходу не работают.

Просто каждое возможное расположение крестиков на поле $2^n$ вариантов это состояния. Перебираем им по убыванию количества крестиков. Тут состояние 1им числом не описать.

[waxtep]

Для нечетного $n>5$, кажется, можно так рассуждать: если первый надеется выиграть, то рано или поздно должен поставить крестик в середину, иначе второй его замучает "зеркальной" стратегией. А второй, в свою очередь, должен поставить крестик рядом, по той же причине. Пусть это будут два первых полухода, и тогда игровое поле $n=2m+1$ таки распадается на два независимых поля $\{m-2,m-3\}$, и хочется снова призвать на помощь тех двух ученых мужей. Дальше необоснованная спекуляция: каким бы ни было значение $F$ для поля нечетного размера, для четного оно ноль, и $F\oplus0=F$. И тогда похоже для нечетного $n$ выиграет первый, если на каком-то ходе не вылезет трешка (поле размера $3$; три крестика к ряду ставить опасно). А второй выиграет для нечетных $n$ в диапазонах $2^k-5\div2^k+2^{k-2}-7,k>3$, т.е. $11,13,27\div33,59\div73,\ldots$

-- 05.01.2025, 22:42 --

Ах нет, не все так просто, например, $n=11$: первый ставит крестик в клетку $4$, второй зеркалит и ставит в $8$. Теперь первый ставит крестик в серединку, в $6$, - и второй уже не имеет возможности поставить крестик рядом