Тема . Применение классических комбинаторных методов к разным задачам

Полуинвариант

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела применение классических комбинаторных методов к разным задачам
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#98555

В клетках таблицы 8× 8  расставлены натуральные числа. Докажите, что у некоторых из этих чисел можно сменить знак таким образом, чтобы каждое из чисел отличалось по знаку от суммы чисел, стоящих в соседних с ним (по стороне или углу) клетках. (Ноль считается отличающимся по знаку от любого ненулевого числа).

Подсказки к задаче

Подсказка 1

Иногда в комбинаторных задачах на доказательство в случае отсутствия некоторого процесса его нужно организовать. Как это можно сделать в данной задаче?

Подсказка 2

Рассмотрим исходную доску и каждую минуту, если еще существуют клетки, для которых не выполнено рассматриваемое условие, будем выбирать любую из них и менять знак числа на ней. Так, нам достаточно доказать, что данный процесс является конечным. Что чаще всего позволяет доказывать конечность некоторого процесса?

Подсказка 3

Поиск полуинварианта. Достаточно найти некоторую величину, которая будет уменьшаться, если мы будем менять знаки числа внутри клеток на различные. Какие бинарные операции минимальны при рассмотрении всех возможных знаков аргументов в том случае, если знаки аргументов различны?

Подсказка 4

Произведение. Нам необходимо следить за всеми произведениями чисел на соседних клетках. Проще всего, объединить их в единственное значение, можно с помощью суммы. Таким образом, наш полуинвариант - сумма всевозможных произведений чисел на соседних клетках.

Подсказка 5

Мы уже поняли, что рассматриваемая величина уменьшается с каждым шагом алгоритма. Для завершение доказательства, осталось проверить, что величина ограничена при заданных на доске числах.

Показать доказательство

Рассмотрим величину S,  равную сумме всех произведений вида ab,  где числа a  и b  стоят в соседних клетках. Пусть мы пока не добились необходимого условия на знаки. Тогда есть число x,  сумма Sx  его соседей имеет тот же знак: xSx > 0  (неравенство строгое, поскольку числа целые(но ненулевые), а сумма не 0).  Тогда поменяем знак у x.  Теперь xSx <0,  а, значит, вся величина S  тоже уменьшилась. Она ограничена снизу(возьмём все слагаемые из S  со знаком минус и получим минимум), поэтому процесс остановится, и мы получим расстановку, требуемую в условии.

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!