Задача 2.5. Плюсы, минусы и кратное 11

Что делает один ход

Назовём каждый знак по числу, перед которым он стоит: «знак перед $2$», «знак перед $3$», …, «знак перед $12$». Всего знаков $11$.

Рядом с числом $5$ стоят два знака: знак перед $5$ (слева) и знак перед $6$ (справа). Ход «у числа $5$» меняет оба на противоположные. Например, кусок примера $4+5-6$ после такого хода станет $4-5+6$ (рисунок ниже).

Так же ход у любого числа $k$ от $2$ до $11$ меняет знак перед $k$ и знак перед следующим числом $k+1$. У числа $1$ рядом только один знак — справа, у числа $12$ тоже один — слева. Поменять «два знака рядом» с ними нельзя, поэтому ходы бывают только у чисел $2, 3, \ldots, 11$ — всего $10$ разных ходов.

Зачем это нужно: дальше мы будем следить за каждым знаком отдельно, и важно точно знать, какие знаки задевает каждый ход.

Какой ответ, кратный 11, выбрать

Знаки в начале случайные, поэтому нужен способ, который сработает для любой расстановки. Удобнее всего заранее выбрать расстановку знаков с ответом, кратным $11$ (назовём её целью), и научиться приводить к ней любое начало. Подберём такую цель.

Если везде плюсы, ответ равен

Складывать удобно парами: $1+12=13$, $2+11=13$, …, $6+7=13$ — это $6$ пар по $13$, то есть $6\cdot13=78$.

Теперь поставим минус перед каким-нибудь числом, например перед $6$. Раньше $6$ прибавлялось, а теперь вычитается: ответ уменьшается на $6+6=12$ и становится $78-12=66$. Так с каждым минусом: минус перед числом $a$ уменьшает ответ на $2\cdot a$. Значит,

Из $78$ вычитается чётное число, поэтому ответ всегда чётный. Ближайшее к $78$ число, кратное $11$, — это $77$, но оно нечётное и не получится. Следующее — $66=6\cdot11$. Для него сумма чисел с минусом должна быть $(78-66):2=6$. Подходят такие расстановки:

• минус только перед $6$: $1+2+3+4+5-6+7+8+9+10+11+12=66$;
• минусы перед $2$ и $4$ (их сумма $2+4=6$): $1-2+3-4+5+6+7+8+9+10+11+12=66$.

Эти две расстановки и будут нашими целями. Почему нужны обе, объяснит следующий шаг.

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

Что не меняется при ходах

Посмотрим, что ход делает с количеством минусов. Ход переворачивает два знака, и вариантов всего три (рисунок ниже):

• было «$+$, $+$» — стало «$-$, $-$»: минусов на $2$ больше;
• было «$-$, $-$» — стало «$+$, $+$»: минусов на $2$ меньше;
• было «$+$, $-$» или «$-$, $+$» — знаки поменялись местами: минусов столько же.

Число минусов меняется на $2$ или не меняется. Поэтому если в начале минусов было нечётное число (например, $5$), то и после любых ходов их будет нечётное число, а если чётное — то чётное. Величину, которая не меняется при ходах, называют инвариантом; здесь инвариант — чётность числа минусов.

Теперь ясно, зачем две цели. В цели «минус только перед $6$» один минус — нечётное число, в цели «минусы перед $2$ и $4$» два — чётное. Если в начале минусов нечётное число, идём к первой цели, если чётное — ко второй. В цель другой чётности не попасть никакими ходами.

Как догадаться посчитать минусы: если в модели «Сыграй сам» идти от примера, с которого она начинается, к цели «минус только перед $6$», знаки перед $2$, $3$, …, $11$ сделать как у цели удаётся, а перед $12$ упрямо остаётся минус. Значит, при ходах что-то не меняется. Ход переворачивает ровно два знака — естественно проверить, как он меняет число минусов.

Исправляем знаки слева направо

Цель выбрана — будем исправлять знаки по одному, начиная слева.

Знак перед $2$ меняется только при ходе у числа $2$: ход у $3$ меняет знаки перед $3$ и перед $4$, а остальные ходы — знаки ещё правее. Поэтому начинаем с него: если знак перед $2$ не такой, как в цели, делаем ход у числа $2$. Заодно поменяется знак перед $3$, но его мы ещё не проверяли.

Дальше смотрим на знак перед $3$: не совпадает с целью — ход у числа $3$. Знак перед $2$ этот ход уже не трогает. И так по очереди: для $k=2, 3, \ldots, 11$ сравниваем знак перед $k$ с целью и при несовпадении делаем ход у числа $k$. Ход у $k$ меняет только знаки перед $k$ и перед $k+1$, поэтому всё, что левее, уже исправлено и больше не портится.

Каждое из чисел $2, 3, \ldots, 11$ проверяется один раз, значит, ходов не больше $10$ — меньше разрешённых $12$. После прохода знаки перед $2, 3, \ldots, 11$ совпадают с целью.

Пример — на рисунке ниже. Начало:

Минусов $5$ — нечётно, цель «минус только перед $6$». Перед $2$ минус, а в цели плюс — ход у $2$; после него минус оказался перед $3$ — ход у $3$, и заодно исчез минус перед $4$. Знаки перед $4$ и $5$ уже как в цели. Перед $6$ в цели минус, а у нас плюс — ход у $6$, он же убирает минус перед $7$. Знаки перед $7$, $8$, $9$, $10$ совпадают с целью, перед $11$ минус — ход у $11$. Всего $4$ хода.

Как догадаться: ход задевает два соседних знака. Если исправлять знаки в одну сторону, каждый ход может испортить только знак, до которого мы ещё не дошли.

Последний знак исправится сам

Знак перед $12$ мы не проверяли: хода у числа $12$ нет. Но он обязательно совпадёт с целью — будет плюсом.

Почему? После прохода все остальные знаки такие же, как в цели. Если бы перед $12$ стоял минус, минусов было бы на один больше, чем в цели: $2$ вместо $1$ или $3$ вместо $2$. Тогда чётность числа минусов была бы не такой, как у цели. Но цель мы выбрали той же чётности, что в начале, а ходы чётность не меняют (шаг 3). Значит, перед $12$ стоит плюс, и пример в точности совпал с целью: ответ $66=6\cdot11$.

В примере так и вышло: минус перед $12$ пропал сам, когда мы сделали ход у числа $11$ ради знака перед $11$.

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