|
|
 |
Условие
В сейфе 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|.
Доказательство. Заметим, что при нашем действии цена уменьшается на
Первый способ. Пусть 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|. Значит, цену расположения нельзя уменьшить на число, большее чем количество заплаченных рублей. Таким образом, цена расположения – это наименьшее число рублей, которое надо заплатить, чтобы привести его к требуемому.
