Задание олимпиады: Вернем карточки в порядок с Васей

  Пусть  (b₁, ..., b_n)  – произвольное расположение карточек (здесь b_i – число на карточке в i-й ячейке). Назовём его ценой число

|b₁ – 1| + |b₂ – 2| + ... + |b_n – n|.   Лемма. Для любого расположения  (b₁, ..., b_n),  в котором не все карточки лежат на своих местах, можно поменять местами некоторые две карточки b_i и b_j так, что цена уменьшится ровно на  2|b_i – b_j|.

  Доказательство. Заметим, что при нашем действии цена уменьшается на

|b_i – i| + |b_j – j| – |b_i – j| – |b_j – i| = (|b_i – i| – |b_j – i|) + (|b_j – j| – |b_i – j|).     (*)

  Нетрудно видеть, что для того, чтобы выражение (*) было равно  2|b_i – b_j|,  достаточно выполнения неравенств  i ≤ b_j < b_i ≤ j:  тогда каждая из скобок в (*) будет равна  |b_i – b_j|.  Осталось найти такие индексыiиj.  Первый способ. Пустьj– наибольшее число на карточке, лежащей не в своей ячейке. Карточка с числомb_jтакже лежит не в своей ячейке, так что b_j < j.  Отметим первыеb_jячеек. У нас есть ровноb_jкарточек с числами, не превосходящимиb_j, и одна из них (карточка с числомb_j) уже лежит в неотмеченной ячейке с номером  j < b_j.  Значит, найдётся такая отмеченная ячейкаi, чтоb_i > b_j.  По выбору номераj, имеем  b_i ≤ j,  откуда и следует цепочка неравенств  i ≤ b_j < b_i ≤ j.  Второй способ. Для каждогоkобозначим черезc_kномер ячейки, в которой лежит карточка с числомk(таким образом,  c_bk = k = b_ck).   Пустьs– наименьшее число, при котором  c_s < s;  такое число найдётся, поскольку  c₁+ ... +c_n= 1 + ... +n.  Тогда карточка с числомc_sлежит не в своей ячейке. Пустьt– максимальный номер ячейки, меньшийsи такой, что  c_t ≠ t.  Тогда  c_t > t,  ибо  t < s;  кроме того,  t ≥ c_s  из максимальностиt. Поскольку  k = c_k ≠ c_t  при всех  t < k < s,  из неравенства  c_t > t  следует  c_t ≥ s.  Итак,  c_s ≤ t < s ≤ c_t.  Полагая  i = c_s,  j = c_t,  приходим к требуемому неравенству i ≤ b_j < b_j ≤ j.   Итак, для любого расположения, отличного от требуемого, можно уменьшить его цену на некоторое число a, заплатив ровно a. Продолжая такие действия, мы в результате придём к расположению с нулевой ценой, заплатив в процессе ровно цену исходного расположения.