Миша написал на доске в некотором порядке 21 плюс и 20 минусов. Время от времени Юра подходит к доске, стирает любые два знака и пишет вместо них один, причём если он стёр одинаковые знаки, то вместо них он пишет плюс, а если разные, то минус. После нескольких таких действий на доске остался только один знак. Какой?

Question

Миша написал на доске в некотором порядке 21 плюс и 20 минусов. Время от времени Юра подходит к доске, стирает любые два знака и пишет вместо них один, причём если он стёр одинаковые знаки, то вместо них он пишет плюс, а если разные, то минус. После нескольких таких действий на доске остался только один знак. Какой?

Фото задания

Accepted Answer

Решение:

В начале на доске 21 плюс (+) и 20 минусов (-). Всего знаков: \( 21 + 20 = 41 \).

Рассмотрим, как меняется чётность количества плюсов и минусов при каждой операции:

Случай 1: Стираем два плюса (+) и пишем один плюс (+).
Количество плюсов уменьшается на 1 (21 → 20). Количество минусов не меняется. Общее количество знаков уменьшается на 1 (41 → 40).
Случай 2: Стираем два минуса (-) и пишем один плюс (+).
Количество плюсов увеличивается на 1 (21 → 22). Количество минусов уменьшается на 2 (20 → 18). Общее количество знаков уменьшается на 1 (41 → 40).
Случай 3: Стираем один плюс (+) и один минус (-) и пишем один минус (-).
Количество плюсов уменьшается на 1 (21 → 20). Количество минусов уменьшается на 1 (20 → 19). Общее количество знаков уменьшается на 1 (41 → 40).

Заметим, что в каждом случае количество минусов либо не меняется, либо уменьшается на 2 (то есть остаётся чётным), либо меняется на 1 (20 → 19). Однако, если мы посмотрим на разность между количеством плюсов и минусов:

Случай 1: (+,+ → +)
\( (n_+ - 1) - n_- = (n_+ - n_-) - 1 \)
Случай 2: (-, - → +)
\( (n_+ + 1) - (n_- - 2) = (n_+ - n_-) + 3 \)
Случай 3: (+, - → -)
\( (n_+ - 1) - (n_- - 1) = n_+ - n_- \)

Эти рассуждения с разностью не очень удобны. Рассмотрим чётность количества минусов:

В начале: 20 минусов (чётное число).
Если стираем два плюса и пишем плюс: количество минусов не меняется (остаётся чётным).
Если стираем два минуса и пишем плюс: количество минусов уменьшается на 2 (остаётся чётным).
Если стираем плюс и минус и пишем минус: количество минусов уменьшается на 1.

Вот здесь ошибка в моих рассуждениях. Давайте проанализируем чётность общего числа знаков. Изначально знаков 41 (нечётное). Каждая операция уменьшает общее число знаков на 1. В итоге останется 1 знак. Это не даёт информации.

Рассмотрим чётность количества минусов более внимательно:

Начало: 20 минусов (чётное).
Операция 1: \( ++ \rightarrow + \). \( N_- \) не меняется (чётное). \( N_+ \) уменьшается на 1.
Операция 2: \( -- \rightarrow + \). \( N_- \) уменьшается на 2 (чётное). \( N_+ \) увеличивается на 1.
Операция 3: \( + - \rightarrow - \). \( N_- \) уменьшается на 1 (становится нечётным). \( N_+ \) уменьшается на 1.

Если бы мы всегда стирали два минуса и писали плюс, то количество минусов всегда оставалось бы чётным. Но мы можем стирать и плюс с минусом.

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

Давайте посмотрим на чётность количества минусов.

Изначально: 20 минусов (чётное).

Если стираем два плюса (++, +), количество минусов не меняется. Чётность сохраняется.
Если стираем два минуса (--, +), количество минусов уменьшается на 2. Чётность сохраняется.
Если стираем плюс и минус (+-, -), количество минусов уменьшается на 1. Чётность меняется.

Это означает, что если мы начинаем с чётного числа минусов, то после операции 3, число минусов станет нечётным. А после следующей операции 3, снова чётным.

Ключевой момент: Количество минусов меняется либо на 0 (операция 1), либо на 2 (операция 2), либо на 1 (операция 3).

Рассмотрим чётность числа минусов.

Изначально: 20 минусов (чётное).
Операция 1 (++ → +): Число минусов не меняется. Остаётся чётным.
Операция 2 (-- → +): Число минусов уменьшается на 2. Остаётся чётным.
Операция 3 (+- → -): Число минусов уменьшается на 1. Чётность меняется (чётное → нечётное, нечётное → чётное).

Мы начинаем с чётного числа минусов (20). После каждой операции, чётность числа минусов меняется только в случае операции 3. Поскольку мы выполняем операции много раз, и конечный результат — один знак, мы не можем точно сказать, будет ли он минусом.

Однако, есть другой подход.

Посмотрим на сумму количества плюсов и минусов. Изначально: \( 21 + 20 = 41 \). Каждая операция уменьшает общее количество знаков на 1. В конце останется 1 знак. Это не помогает.

Рассмотрим чётность числа минусов.

Изначально: 20 минусов (чётное).

Если стираем два одинаковых знака (++ или --), то пишем знак того типа, который был стёрт, если стирали плюсы, пишем плюс, если стирали минусы, пишем плюс. (В условии задачи сказано: если стёр одинаковые знаки, то пишет плюс.)

Разберём снова:

Изначально: 21 плюс, 20 минусов.
Операция 1: Стираем два плюса (++), пишем один плюс (+).
\( N_+ \) меняется с 21 на \( 21 - 2 + 1 = 20 \).
\( N_- \) остаётся 20.
Операция 2: Стираем два минуса (--), пишем один плюс (+).
\( N_+ \) меняется с 21 на \( 21 + 1 = 22 \).
\( N_- \) меняется с 20 на \( 20 - 2 = 18 \).
Операция 3: Стираем плюс и минус (+-), пишем один минус (-).
\( N_+ \) меняется с 21 на \( 21 - 1 = 20 \).
\( N_- \) меняется с 20 на \( 20 - 1 = 19 \).

Анализируем чётность количества минусов:

Начало: 20 минусов (чётное).
Операция 1 (++ → +): \( N_- \) остаётся 20 (чётное).
Операция 2 (-- → +): \( N_- \) становится 18 (чётное).
Операция 3 (+- → -): \( N_- \) становится 19 (нечётное).

Мы начинаем с чётного числа минусов. Каждая операция, которая убирает два минуса, сохраняет чётность. Но операция, которая убирает один плюс и один минус, меняет чётность числа минусов.

Пусть \( k_1 \) — число раз, когда выполнена операция 1, \( k_2 \) — число раз, когда выполнена операция 2, \( k_3 \) — число раз, когда выполнена операция 3.

Общее количество знаков уменьшается на 1 при каждом шаге. Всего \( 41 - 1 = 40 \) шагов.

Конечное число минусов \( N'_- \) будет: \( 20 - 2k_2 - k_3 \).

Конечное число плюсов \( N'_+ \) будет: \( 21 - 2k_1 + k_2 + k_3 \).

Ключевая идея: Чётность количества минусов. Изначально 20 (чётное).

Если мы выполняем операцию 1 (++ → +): \( N_- \) не меняется. Чётность сохраняется (чётное).

Если мы выполняем операцию 2 (-- → +): \( N_- \) уменьшается на 2. Чётность сохраняется (чётное).

Если мы выполняем операцию 3 (+- → -): \( N_- \) уменьшается на 1. Чётность меняется (чётное → нечётное).

Итак, если мы когда-либо выполним операцию 3, число минусов станет нечётным. Если мы выполним её ещё раз, оно снова станет чётным.

Рассмотрим остаток от деления количества минусов на 2.

Изначально: \( 20 \bmod 2 = 0 \).

После операции 1 (++ → +): \( N'_- = N_- \). \( N'_- \bmod 2 = N_- \bmod 2 \).

После операции 2 (-- → +): \( N'_- = N_- - 2 \). \( N'_- \bmod 2 = (N_- - 2) \bmod 2 = N_- \bmod 2 \).

После операции 3 (+- → -): \( N'_- = N_- - 1 \). \( N'_- \bmod 2 = (N_- - 1) \bmod 2 \).

Это означает, что чётность числа минусов меняется только при выполнении операции 3.

Мы начинаем с чётного числа минусов (20). В конце останется только один знак. Этот знак может быть либо плюсом, либо минусом.

Если в конце остался минус, то \( N'_- = 1 \). \( 1 \bmod 2 = 1 \) (нечётное).

Если в конце остался плюс, то \( N'_- = 0 \). \( 0 \bmod 2 = 0 \) (чётное).

Изначально \( N_- \) чётное. Чётность \( N_- \) меняется только при выполнении операции 3 (+- → -). Если операция 3 выполнена чётное число раз, то \( N_- \) останется чётным. Если операция 3 выполнена нечётное число раз, то \( N_- \) станет нечётным.

Важный момент: Общее число знаков уменьшается на 1 на каждом шаге. Всего \( 41 - 1 = 40 \) шагов.

Известно, что \( N_+ + N_- = \text{общее число знаков} \).

Рассмотрим разность \( N_+ - N_- \).

Операция 1 (++ → +): \( (N_+ - 2 + 1) - N_- = (N_+ - N_-) - 1 \). Разность уменьшается на 1.
Операция 2 (-- → +): \( (N_+ + 1) - (N_- - 2) = (N_+ - N_-) + 3 \). Разность увеличивается на 3.
Операция 3 (+- → -): \( (N_+ - 1) - (N_- - 1) = N_+ - N_- \). Разность не меняется.

Итак, при операции 3 разность \( N_+ - N_- \) остаётся неизменной. При операции 1 она уменьшается на 1, при операции 2 — увеличивается на 3.

Рассмотрим разность по модулю 2.

\( N_+ - N_- \bmod 2 \).

Начало: \( 21 - 20 = 1 \). \( 1 \bmod 2 = 1 \).
Операция 1 (++ → +): \( (N_+ - N_-) - 1 \). \( (1 - 1) \bmod 2 = 0 \). Чётность разности меняется.
Операция 2 (-- → +): \( (N_+ - N_-) + 3 \). \( (1 + 3) \bmod 2 = 4 \bmod 2 = 0 \). Чётность разности меняется.
Операция 3 (+- → -): \( N_+ - N_- \). \( 1 \bmod 2 = 1 \). Чётность разности сохраняется.

Ключевой момент: Рассмотрим чётность числа минусов.

Изначально 20 минусов (чётное).

Если стираем два плюса (++ → +), количество минусов не меняется. Чётность сохраняется.

Если стираем два минуса (-- → +), количество минусов уменьшается на 2. Чётность сохраняется.

Если стираем плюс и минус (+- → -), количество минусов уменьшается на 1. Чётность меняется.

Мы начинаем с чётного числа минусов. Если мы никогда не выполняем операцию 3 (+- → -), то число минусов останется чётным. Если мы выполним операцию 3 нечётное число раз, то число минусов станет нечётным. Если мы выполним её чётное число раз, то число минусов снова станет чётным.

Остаётся один знак.

Если остался плюс, то \( N_- = 0 \) (чётное).

Если остался минус, то \( N_- = 1 \) (нечётное).

Рассмотрим чётность количества плюсов.

Изначально: 21 плюс (нечётное).

Операция 1 (++ → +): \( N_+ \) уменьшается на 1. Чётность меняется (нечётное → чётное).

Операция 2 (-- → +): \( N_+ \) увеличивается на 1. Чётность меняется (нечётное → чётное).

Операция 3 (+- → -): \( N_+ \) уменьшается на 1. Чётность меняется (нечётное → чётное).

В каждом случае чётность числа плюсов меняется!

Мы начинаем с нечётного числа плюсов (21). После одной операции оно становится чётным. После второй — нечётным, и так далее.

Всего будет \( 41 - 1 = 40 \) операций. Чётность числа плюсов будет меняться 40 раз. Если начать с нечётного, после 40 изменений (чётное число изменений) оно снова станет нечётным.

Значит, в конце количество плюсов будет нечётным.

Оставшийся знак — это либо плюс, либо минус.

Если остался минус, то \( N'_+ = 0 \) (чётное).

Если остался плюс, то \( N'_+ = 1 \) (нечётное).

Так как в конце количество плюсов должно быть нечётным, единственная возможность — это 1 плюс.

Следовательно, останется плюс.

Проверим:

Изначально: 21 плюс, 20 минусов. \( N_+ \) — нечётное, \( N_- \) — чётное.

Операция 1 (++ → +): \( N_+ \) → \( N_+ - 1 \) (нечётное → чётное). \( N_- \) → \( N_- \) (чётное → чётное). Итого: \( N_+ \) чётное, \( N_- \) чётное.

Операция 2 (-- → +): \( N_+ \) → \( N_+ + 1 \) (нечётное → чётное). \( N_- \) → \( N_- - 2 \) (чётное → чётное). Итого: \( N_+ \) чётное, \( N_- \) чётное.

Операция 3 (+- → -): \( N_+ \) → \( N_+ - 1 \) (нечётное → чётное). \( N_- \) → \( N_- - 1 \) (чётное → нечётное). Итого: \( N_+ \) чётное, \( N_- \) нечётное.

Теперь будем применять операции последовательно, пока не останется один знак.

Начало: (21, 20) — (неч, чет)

Шаг 1. Выполним операцию 1 (++ → +) 10 раз: (21-10, 20) = (11, 20) — (неч, чет)

Шаг 2. Выполним операцию 2 (-- → +) 10 раз: (11+10, 20-20) = (21, 0) — (неч, чет)

Теперь у нас 21 плюс и 0 минусов. Осталась только операция 1 (++ → +). Каждый раз число плюсов уменьшается на 1.

21 → 20 → 19 → ... → 2 → 1.

Последний знак будет плюс.

Рассмотрим другой путь:

Начало: (21, 20) — (неч, чет)

Шаг 1. Выполним операцию 3 (+- → -) 20 раз: (21-20, 20-20) = (1, 0). — (неч, чет)

Это неверно. Операция 3 меняет чётность числа минусов. Если начать с 20 (чётное), и выполнить операцию 3 20 раз (чётное число раз), то число минусов должно остаться чётным.

Правильное рассуждение:

Пусть \( n_+ \) — количество плюсов, \( n_- \) — количество минусов.

Изменение \( n_- \):

\( ++ \rightarrow + \): \( \triangle n_- = 0 \)
\( -- \rightarrow + \): \( \triangle n_- = -2 \)
\( + - \rightarrow - \): \( \triangle n_- = -1 \)

Заметим, что \( \triangle n_- \) может быть 0, -1, -2.

Изначально \( n_- = 20 \) (чётное).

Если последнее действие — операция 3 (+- → -), то \( n_- \) меняется на -1. Из чётного оно станет нечётным. В конце останется 1 минус. \( n'_- = 1 \).

Если последнее действие — операция 1 (++ → +) или 2 (-- → +), то \( n_- \) меняется на 0 или -2. Чётность остаётся той же. То есть, если мы начинаем с чётного \( n_- \), и последние действия не были операцией 3, то \( n_- \) будет чётным. В конце останется 0 минусов (плюс).

Ключ в том, что чётность числа минусов сохраняется, если не выполняется операция (+- → -).

Если мы выполним операцию (+- → -) любое число раз, чётность числа минусов будет меняться.

Единственный инвариант, который помогает:

Рассмотрим количество минусов по модулю 2.

Изначально: \( n_- = 20 \), \( n_- \bmod 2 = 0 \).

\( ++ \rightarrow + \): \( n'_- = n_- \). \( n'_- \bmod 2 = n_- \bmod 2 \).
\( -- \rightarrow + \): \( n'_- = n_- - 2 \). \( n'_- \bmod 2 = n_- \bmod 2 \).
\( + - \rightarrow - \): \( n'_- = n_- - 1 \). \( n'_- \bmod 2 = (n_- - 1) \bmod 2 \).

Таким образом, чётность числа минусов меняется только при выполнении операции \( + - \rightarrow - \). Если эту операцию выполнить нечётное число раз, то \( n_- \) станет нечётным. Если чётное число раз — останется чётным.

В конце остаётся один знак.

Если остался минус, то \( n'_- = 1 \) (нечётное).

Если остался плюс, то \( n'_- = 0 \) (чётное).

Поскольку мы начинаем с чётного числа минусов (20), и хотим получить либо 0, либо 1 минус в конце, это означает, что чтобы получить 1 минус (нечётное), мы должны были выполнить операцию (+- → -) нечётное число раз. Чтобы получить 0 минусов (чётное), мы должны были выполнить операцию (+- → -) чётное число раз.

Рассмотрим количество плюсов.

Изначально: \( n_+ = 21 \) (нечётное).

\( ++ \rightarrow + \): \( n'_+ = n_+ - 1 \) (чётность меняется).
\( -- \rightarrow + \): \( n'_+ = n_+ + 1 \) (чётность меняется).
\( + - \rightarrow - \): \( n'_+ = n_+ - 1 \) (чётность меняется).

Каждая операция меняет чётность числа плюсов!

Всего выполняется \( 41 - 1 = 40 \) операций.

Начало: \( n_+ = 21 \) (нечётное).

После 1-й операции: \( n_+ \) становится чётным.

После 2-й операции: \( n_+ \) становится нечётным.

После 40-й (чётное число) операции \( n_+ \) будет нечётным.

В конце остаётся один знак.

Если остался минус, то \( n'_+ = 0 \) (чётное).

Если остался плюс, то \( n'_+ = 1 \) (нечётное).

Так как в конце \( n'_+ \) должно быть нечётным, то единственный вариант — это \( n'_+ = 1 \).

Следовательно, последний оставшийся знак — плюс.

Ответ: Плюс