#8 Игры и стратегии I

При ходах \(1\) или \(2\) проигрышны позиции \(0,3,6,9,12,\ldots\). Из кратного \(3\) любой ход оставляет не кратное \(3\), а из любого другого остатка можно оставить кратное \(3\). Так как \(14\equiv2\pmod3\), первый берет \(2\) камня и оставляет \(12\). Затем он дополняет ход соперника до \(3\) камней.

Проигрышны кратные \(4\). Число \(20\) кратно \(4\), значит первый игрок в проигрышной позиции. Что бы он ни взял, второй берет столько, чтобы за два хода было взято \(4\) камня. Поэтому второй сделает последний ход.

Первый игрок сначала прибавляет \(1\). После хода соперника на \(a\), где \(1\le a\le4\), первый прибавляет \(5-a\). Тогда после ходов первого суммы будут \(1,6,11,16,21\). Поэтому первый выигрывает.

После каждого хода первого второй берет столько же камней из другой кучи. Поэтому после хода второго кучи снова равны. Если первый смог взять камни из одной кучи, то в другой куче столько же камней, и ответ второго легален. Значит второй не останется без хода раньше первого и сделает последний ход.

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

Так как можно взять от \(1\) до \(4\), проигрышны кратные \(5\). Число \(37\) дает остаток \(2\) по модулю \(5\). Первый берет \(2\) камня и оставляет \(35\). После этого на ход соперника \(a\) первый отвечает \(5-a\), снова оставляя кратное \(5\).

Если остался \(1\) камень, игрок на ходе проигрывает. Далее проигрышные позиции повторяются через \(4\): \(1,5,9,\ldots\). Число \(28\equiv0\pmod4\), поэтому первый берет \(3\) камня и оставляет \(25\equiv1\pmod4\). Затем он дополняет ход соперника до \(4\), пока сопернику не останется один камень.

Так как \(50\equiv1\pmod7\), первый начинает с \(1\). Если второй прибавил \(a\), первый прибавляет \(7-a\). Тогда после ходов первого сумма каждый раз увеличивается на \(7\): \(1,8,15,22,29,36,43,50\). Первый выигрывает.

Второй разбивает числа на пары \((1,20),(2,19),\ldots,(10,11)\). Каждый раз, когда первый берет число из пары, второй берет второе число этой пары. В каждой паре сумма равна \(21\), и каждому игроку достается ровно одно число из каждой пары. Поэтому итоговые суммы равны.

После хода первого второй кладет домино в клетки, центрально-симметричные занятым. На доске \(6\times6\) ни одно домино не совпадает со своим центральным отражением, а отражение соседних клеток снова соседние клетки. Если отраженные клетки были бы заняты раньше, то по симметрии были бы заняты и клетки хода первого, что невозможно. Значит ответ всегда легален, и второй делает последний ход.

После \(k\) ходов занято ровно \(k\) строк и \(k\) столбцов. Если \(k<7\), остается свободная строка и свободный столбец, на их пересечении можно поставить ладью. Поэтому игра всегда длится ровно \(7\) ходов. Седьмой ход делает первый игрок, значит он выигрывает.

В начале есть \(1\) кусок, а в конце должно быть \(24\) единичных квадратика. Каждый ход увеличивает число кусков ровно на \(1\). Поэтому всего будет \(24-1=23\) хода. Нечетный ход делает первый игрок, значит он выигрывает.

Позиции с равными кучами проигрышны: соперник может копировать ход в другой куче. Поэтому первый должен уменьшить кучу \(17\) до \(12\), взяв \(5\) камней. После этого на любой ход второго первый отвечает таким же ходом в другой куче и выигрывает.

Кратные \(3\) проигрышны: из них ходы \(1,2,4\) ведут к остаткам \(2,1,2\) по модулю \(3\), а из любого не кратного \(3\) можно взять \(1\) или \(2\), чтобы оставить кратное \(3\). Так как \(30\) кратно \(3\), первый игрок проигрывает при правильной игре.

Проверим позиции с остатками \(0\) и \(2\) по модулю \(7\). Из них ходы \(1,3,4\) не ведут снова к остаткам \(0\) или \(2\). Из любого другого остатка можно попасть в \(0\) или \(2\): из \(1\) взять \(1\), из \(3\) взять \(1\), из \(4\) взять \(4\), из \(5\) взять \(3\), из \(6\) взять \(4\). Значит проигрышны позиции \(0\) и \(2\) по модулю \(7\). Так как \(31\equiv3\pmod7\), первый берет \(1\) камень и оставляет \(30\equiv2\pmod7\).

Второй игрок после каждого хода первого на \(a\) прибавляет \(10-a\). Тогда после ходов второго суммы будут \(10,20,30,\ldots,100\). Поэтому второй игрок достигнет \(100\) и выиграет.

После \(k\) ходов занято \(k\) строк и \(k\) столбцов. Пока \(k<8\), есть свободная строка и свободный столбец, значит можно поставить еще одну ладью. После \(8\) ходов свободных строк не останется, и ход невозможен. Игра длится ровно \(8\) ходов, значит выигрывает второй игрок.

Позиции с остатками \(0\) и \(1\) по модулю \(7\) проигрышны: ходы \(2,3,5\) из них не ведут снова в остатки \(0\) или \(1\). Из остатка \(2\) можно взять \(2\), из \(3\) взять \(2\), из \(4\) взять \(3\), из \(5\) взять \(5\), из \(6\) взять \(5\), оставляя \(0\) или \(1\). Так как \(52\equiv3\pmod7\), первый берет \(2\) камня и оставляет \(50\equiv1\pmod7\).

Если сумма \(63\), любой ход делает сумму не меньше \(64\), и игрок проигрывает. Значит \(63\) проигрышная позиция. Предыдущие проигрышные позиции отличаются на \(6\): \(57,51,\ldots,3\). Из любой такой позиции любой ход ведет между двумя соседними проигрышными позициями, а из любой другой можно попасть в ближайшую проигрышную. Начальная сумма \(0\), первый прибавляет \(3\) и оставляет проигрышную позицию. Затем он дополняет ходы соперника до \(6\).

Если остался \(1\) камень, игрок на ходе проигрывает. Поэтому проигрышные позиции имеют вид \(1,6,11,\ldots\), то есть \(1\pmod5\). Так как \(47\equiv2\pmod5\), первый берет \(1\) камень и оставляет \(46\equiv1\pmod5\). Далее он дополняет ход соперника до \(5\).

Вычислим ним-сумму: \(3\oplus4\oplus5=2\). Нужно сделать ее равной \(0\). Если уменьшить кучу \(3\) до \(1\), получится \(1\oplus4\oplus5=0\). Дальше после любого хода соперника ним-сумма станет ненулевой; можно уменьшить одну кучу так, чтобы снова получить ним-сумму \(0\). Поэтому выигрышный ход: взять \(2\) камня из кучи \(3\).

Для ходов от \(1\) до \(7\) проигрышны кратные \(8\). Число \(2026\equiv2\pmod8\). Первый берет \(2\) камня и оставляет \(2024\), кратное \(8\). После этого он отвечает на ход \(a\) ходом \(8-a\), каждый раз возвращая сопернику кратное \(8\).

Второй отвечает на каждое домино первого центрально-симметричным домино. Центральная клетка удалена, поэтому ни одна оставшаяся клетка не переходит сама в себя. Отражение двух соседних клеток снова две соседние клетки. Если отраженное домино уже было занято, то по стратегии симметрии ранее было бы занято и домино, только что поставленное первым, что невозможно. Поэтому ответ второго всегда легален, и второй делает последний ход.

В двоичной записи \(7=0111\), \(11=1011\), \(13=1101\). Ним-сумма равна \(0111\oplus1011\oplus1101=0001\). Нужно уменьшить одну кучу так, чтобы ним-сумма стала \(0\). Например, уменьшим \(13\) до \(12\), потому что \(7\oplus11\oplus12=0\). После этого, если соперник изменит одну кучу, ним-сумма станет ненулевой. В куче, где стоит старший единичный бит этой суммы, можно уменьшить число так, чтобы общая ним-сумма снова стала \(0\). Повторяя это, первый игрок каждый раз возвращает сопернику нулевую ним-сумму и в конце берет последний камень.