ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64771
Темы:    [ Процессы и операции ]
[ Принцип крайнего (прочее) ]
[ Свойства модуля. Неравенство треугольника ]
Сложность: 4
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

В сейфе n ячеек с номерами от 1 до n. В каждой ячейке первоначально лежала карточка с её номером. Вася переложил карточки в некотором порядке так, что в i-й ячейке оказалась карточка с числом ai. Петя может менять местами любые две карточки с номерами x и y, платя за это  2|x – y|  рублей. Докажите, что Петя сможет вернуть все карточки на исходные места, заплатив не более  |a1 – 1| + |a2 – 2| + ... + |an – n|  рублей.


Решение

  Пусть  (b1, ..., bn)  – произвольное расположение карточек (здесь bi – число на карточке в i-й ячейке). Назовём его ценой число
|b1 – 1| + |b2 – 2| + ... + |bn – n|.

  Лемма. Для любого расположения  (b1, ..., bn),  в котором не все карточки лежат на своих местах, можно поменять местами некоторые две карточки bi и bj так, что цена уменьшится ровно на  2|bi – bj|.
  Доказательство. Заметим, что при нашем действии цена уменьшается на

|bi – i| + |bj – j| – |bi – j| – |bj – i| = (|bi – i| – |bj – i|) + (|bj – j| – |bi – j|).     (*)
  Нетрудно видеть, что для того, чтобы выражение (*) было равно  2|bi – bj|,  достаточно выполнения неравенств  i ≤ bj < bi ≤ j:  тогда каждая из скобок в (*) будет равна  |bi – bj|.  Осталось найти такие индексы i и j.
  Первый способ. Пусть j – наибольшее число на карточке, лежащей не в своей ячейке. Карточка с числом bj также лежит не в своей ячейке, так что
bj < j.  Отметим первые bj ячеек. У нас есть ровно bj карточек с числами, не превосходящими bj, и одна из них (карточка с числом bj) уже лежит в неотмеченной ячейке с номером  j < bj.  Значит, найдётся такая отмеченная ячейка i, что bi > bj.  По выбору номера j, имеем  bi ≤ j,  откуда и следует цепочка неравенств  i ≤ bj < bi ≤ j.
  Второй способ. Для каждого k обозначим через ck номер ячейки, в которой лежит карточка с числом k (таким образом,  cbk = k = bck).
  Пусть s – наименьшее число, при котором  cs < s;  такое число найдётся, поскольку  c1 + ... + cn = 1 + ... + n.  Тогда карточка с числом cs лежит не в своей ячейке. Пусть t – максимальный номер ячейки, меньший s и такой, что  ct ≠ t.  Тогда  ct > t,  ибо  t < s;  кроме того,  t ≥ cs  из максимальности t. Поскольку  k = ck ≠ ct  при всех  t < k < s,  из неравенства  ct > t  следует  ct ≥ s.  Итак,  cs ≤ t < s ≤ ct.  Полагая  i = cs,  j = ct,  приходим к требуемому неравенству
i ≤ bj < bj ≤ j.

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

Замечания

1. Существуют и другие способы доказательства леммы.

2. Каждая скобка в выражении (*) не превосходит  |bi – bj|.  Значит, цену расположения нельзя уменьшить на число, большее чем количество заплаченных рублей. Таким образом, цена расположения – это наименьшее число рублей, которое надо заплатить, чтобы привести его к требуемому.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2013-2014
этап
Вариант 5
класс
Класс 10
задача
Номер 10.3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .