Полуинвариант
Ошибка.
Попробуйте повторить позже
В клетках таблицы расставлены натуральные числа. Докажите, что у некоторых из этих чисел можно сменить знак таким образом, чтобы каждое из чисел отличалось по знаку от суммы чисел, стоящих в соседних с ним (по стороне или углу) клетках. (Ноль считается отличающимся по знаку от любого ненулевого числа).
Подсказка 1
Иногда в комбинаторных задачах на доказательство в случае отсутствия некоторого процесса его нужно организовать. Как это можно сделать в данной задаче?
Подсказка 2
Рассмотрим исходную доску и каждую минуту, если еще существуют клетки, для которых не выполнено рассматриваемое условие, будем выбирать любую из них и менять знак числа на ней. Так, нам достаточно доказать, что данный процесс является конечным. Что чаще всего позволяет доказывать конечность некоторого процесса?
Подсказка 3
Поиск полуинварианта. Достаточно найти некоторую величину, которая будет уменьшаться, если мы будем менять знаки числа внутри клеток на различные. Какие бинарные операции минимальны при рассмотрении всех возможных знаков аргументов в том случае, если знаки аргументов различны?
Подсказка 4
Произведение. Нам необходимо следить за всеми произведениями чисел на соседних клетках. Проще всего, объединить их в единственное значение, можно с помощью суммы. Таким образом, наш полуинвариант - сумма всевозможных произведений чисел на соседних клетках.
Подсказка 5
Мы уже поняли, что рассматриваемая величина уменьшается с каждым шагом алгоритма. Для завершение доказательства, осталось проверить, что величина ограничена при заданных на доске числах.
Рассмотрим величину равную сумме всех произведений вида где числа и стоят в соседних клетках. Пусть мы пока не добились необходимого условия на знаки. Тогда есть число сумма его соседей имеет тот же знак: (неравенство строгое, поскольку числа целые(но ненулевые), а сумма не Тогда поменяем знак у Теперь а, значит, вся величина тоже уменьшилась. Она ограничена снизу(возьмём все слагаемые из со знаком минус и получим минимум), поэтому процесс остановится, и мы получим расстановку, требуемую в условии.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!