Олимпиадная задача: минимальная сумма в первой строке прямоугольной таблицы 9×2004

  Оценка. Переставив, если нужно, столбцы, будем далее считать, что числа в первой строке стоят в неубывающем порядке. Пусть a_i – i-е число первой строки. Рассмотрим сумму  S = (a₁ – 1) + (a₂ – 1) + (a₃ – 1) + (a₄ – 2) + ... + (a_i – (i – 2)) + ... + (a₂₀₀₃ – 2001) + (a₂₀₀₄ – 2001).

  Докажем, что  S ≥ 0.  Обозначим i-е слагаемое в нашей сумме через d_i. Если в этой сумме нет отрицательных членов, все очевидно. Ясно, что  a₂₀₀₄ ≥ 2001,  a₂ ≥ a₁ ≥ 1,  то есть  d₁, d₂, d₂₀₀₄ ≥ 0.

  Пусть  d_i < 0,  то есть  a_i ≤ i – 3.  Тогда в i первых столбцах содержатся только числа от 1 до i, следовательно, там содержатся все такие числа. Отсюда следует, что  a_i = i – 3,  a_i+1 ≥ i + 1,  и  d_i + d_i+1 > 0.

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

  Итак,  a₁ + a₂ + ... + a₂₀₀₄ ≥ 1 + 1 + 1 + 2 + ... + 2001 + 2001 = 2003·2002 : 2 + 1 = 2005004.

  Пример таблицы, для которой оценка достигается: