Инвариант
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В квадрат 
по порядку расставлены числа от 
до 
За ход можно выбрать число, и прибавить к нему 
а из двух соседей,
лежащих с ним на одной прямой, вычесть по 
Или, наоборот: отнять 
и прибавить к двум соседям по 
В конце снова получилась
расстановка чисел от 
до 
Докажите, что она совпала с исходной.
Подсказка 1
Какие инварианты сохраняются при разрешённых операциях?
Подсказка 2
Рассмотрим S — сумму квадратов по всем клеткам.
Подсказка 3
Что происходит с S при горизонтальном ходе (центральная клетка +2, соседи по горизонтали −1)?
Подсказка 4
Что даёт равенство инварианта в начале и в конце?
Подсказка 5
Σ aᵢⱼ² = Σ aᵢⱼ bᵢⱼ (где aᵢⱼ, bᵢⱼ — числа в клетке (i, j) в начальной и конечной расстановке соотвественно), а так как bᵢⱼ — та же перестановка 1 ... 100, то Σ bᵢⱼ² = Σ aᵢⱼ².
Подсказка 6
Рассмотрите Σ (aᵢⱼ − bᵢⱼ)². Что вы получите?
Подсказка 7
Эта сумма равна нулю, откуда следует aᵢⱼ = bᵢⱼ для всех i,j — то есть финальная расстановка совпадает с начальной.
Пусть 
— число в клетке 
в начальный момент времени, где
Пусть 
— число в клетке 
в конечный момент времени.
Рассмотрим в качестве инварианта взвешенную сумму всех чисел на доске
где 
— текущее число в клетке.
Проверим, что при таком выборе весов сумма 
не меняется. Пусть мы совершаем ход в клетке 
число 
изменяется на 
а его соседи (например, по горизонтали) 
и 
изменяются на 
Изменение суммы 
составит:
Если ход совершается с вертикальными соседями 
и 
изменение суммы будет:
Аналогично, если от числа 
отнимается 2, а к соседям прибавляется по 1, изменение суммы также будет равно нулю. Таким образом,
величина 
является инвариантом.
Теперь сравним значения инварианта в начале и в конце. В начальный момент времени 
поэтому:
В конечный момент времени 
поэтому:
Поскольку 
— инвариант, 
откуда следует ключевое равенство:
По условию задачи, конечная расстановка 
также является перестановкой чисел от 1 до 100. Это означает, что
набор чисел 
совпадает с набором чисел 
Следовательно, сумма квадратов чисел в этих наборах должна быть
одинаковой:
Теперь рассмотрим сумму квадратов разностей между начальной и конечной конфигурациями:
Используя равенства 
и 
получаем:
Сумма квадратов действительных чисел равна нулю тогда и только тогда, когда каждый из членов суммы равен нулю. Следовательно,
для всех 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
