#6 Инварианты I

Начальное число чётно, и прибавление \(2\) сохраняет чётность. Число \(99\) нечётно, значит получить его нельзя.

Число орлов меняется на \(-2\), \(0\) или \(2\), значит его чётность сохраняется. Было \(9\) орлов, должно стать \(0\). Нечётность не может стать чётностью.

В начале всего \(15\) камней, в требуемом состоянии \(20\). Так как перенос камня не меняет сумму, получить такое состояние нельзя.

Остаток по модулю \(3\) сохраняется. \(5\equiv2\pmod3\), а \(100\equiv1\pmod3\). Значит получить \(100\) нельзя.

При смене двух знаков число минусов меняется на \(-2\), \(0\) или \(2\). Чётность числа минусов сохраняется. В начале \(0\), в конце должно быть \(3\), невозможно.

Смена двух знаков умножает произведение на \((-1)^2=1\). В начале произведение \(+1\). При \(7\) минусах произведение \(-1\). Значит нельзя.

В начале всего \(14\) фишек, в конце \(15\). Перекладывание фишки сохраняет общее число, поэтому состояние невозможно.

Если среди перевёрнутых \(h\) орлов, число орлов меняется на \(4-2h\), то есть на чётное число. Чётность сохраняется. Было \(15\) орлов, нечётно; \(2\) орла — чётно. Нельзя.

В начале сумма \(11\), в конце сумма \(15\). Операция сохраняет сумму, значит получить нельзя.

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

Смена \(4\) знаков умножает произведение на \((-1)^4=1\). В начале произведение \(+1\), а при одном минусе \(-1\). Нельзя.

За ход сумма меняется на \(1+1-2=0\). Значит сумма вообще сохраняется, а тем более сохраняется её остаток по модулю \(3\).

Если среди выбранных \(h\) включённых ламп, то число включённых меняется на \(100-2h\), чётное число. В начале включённых \(0\), чётно; в конце должно быть \(2025\), нечётно. Нельзя.

За ход общее число фишек меняется на \(4-1=3\), значит остаток суммы по модулю \(3\) не меняется.

В исходной доске \(32\) чёрных и \(32\) белых клетки. Противоположные углы одного цвета, значит после удаления остаётся \(30\) клеток одного цвета и \(32\) другого. Домино всегда покрывает одну чёрную и одну белую клетку, поэтому покрытие невозможно.

Каждый ход меняет \(4\) знака, значит произведение всех \(16\) знаков умножается на \((-1)^4=1\). В начале произведение \(+1\). При ровно одном минусе произведение \(-1\). Нельзя.

Сумма \(1+2+\cdots+10=55\) нечётна. Замена знака у числа \(a\) меняет сумму на \(-2a\), то есть на чётное число. Поэтому чётность суммы сохраняется и остаётся нечётной. Ноль чётен, значит невозможно.

Ход коня меняет цвет клетки. После нечётного числа ходов цвет будет противоположным начальному. \(2025\) нечётно, значит конь будет на чёрной клетке, не на белой.

Чётность числа сохраняется, потому что прибавляются чётные числа. Начальное число \(1\) нечётно, а \(100\) чётно. Получить нельзя.

Каждый ход увеличивает \(x+y\) на \(3\). Значит остаток \(x+y\) по модулю \(3\) сохраняется и равен \(0\). В точке \((10,10)\) сумма координат \(20\equiv2\pmod3\). Попасть нельзя.

Произведение всех \(36\) чисел сохраняется: за ход оно умножается на \((-1)^6=1\). В начале произведение \(1\). В таблице с одной \(-1\) произведение \(-1\). Значит такая таблица недостижима.

Каждый ход коня меняет цвет клетки. После \(15\) ходов, поскольку \(15\) нечётно, конь окажется на клетке противоположного цвета. Исходная клетка чёрная, значит вернуться на неё нельзя.

За ход сумма меняется на \(2+2-1=3\), значит её остаток по модулю \(3\) сохраняется. В начале сумма \(3\equiv0\pmod3\). В конце сумма \(30\equiv0\pmod3\), этот инвариант не запрещает. Попробуем сумму квадратов по модулю \(3\): числа \(1\) и \(10\) сравнимы по модулю \(3\), а операция меняет остатки двух чисел на \(-1\) и одного на \(-1\), то есть все три остатка уменьшаются на \(1\). После каждого хода все три числа остаются равными по модулю \(3\). В начале они все \(1\), в конце \(10\equiv1\), инвариант тоже не запрещает. Значит по этим инвариантам запрета нет; действительно, состояние достижимо: применим ход три раза, каждый раз вычитая из разной координаты, все координаты увеличатся на \(3\). Повторив три таких цикла, получим \((10,10,10)\).

Число инверсий в начале равно \(0\). Каждый соседний обмен меняет чётность числа инверсий. После \(27\) ходов чётность инверсий должна быть нечётной. Но в строке \(87654321\) число инверсий равно \(C(8,2)=28\), оно чётно. Противоречие, значит ровно за \(27\) ходов получить нельзя.