|
|
 |
Условие
В прямоугольной таблице 9 строк и 2004 столбца. В её клетках расставлены числа от 1 до 2004, каждое – по 9 раз. При этом в каждом столбце числа различаются не более чем на 3. Найдите минимальную возможную сумму чисел в первой строке.
Решение
Оценка. Переставив, если нужно, столбцы, будем далее считать, что числа в первой строке стоят в неубывающем порядке. Пусть ai – i-е число первой строки. Рассмотрим сумму S = (a1 – 1) + (a2 – 1) + (a3 – 1) + (a4 – 2) + ... + (ai – (i – 2)) + ... +
(a2003 – 2001) + (a2004 – 2001).
Докажем, что S ≥ 0. Обозначим i-е слагаемое в нашей сумме через di. Если в этой сумме нет отрицательных членов, все очевидно. Ясно, что a2004 ≥ 2001, a2 ≥ a1 ≥ 1, то есть d1, d2, d2004 ≥ 0.
Пусть di < 0, то есть ai ≤ i – 3. Тогда в i первых столбцах содержатся только числа от 1 до i, следовательно, там содержатся все такие числа. Отсюда следует, что ai = i – 3, ai+1 ≥ i + 1, и di + di+1 > 0.
Таким образом, для любого отрицательного di сумма его со следующим членом положительна, поэтому, объединив такие слагаемые в пары, получаем сумму неотрицательных слагаемых.
Итак, a1 + a2 + ... + a2004 ≥ 1 + 1 + 1 + 2 + ... + 2001 + 2001 = 2003·2002 : 2 + 1 = 2005004.
Пример таблицы, для которой оценка достигается:
(два первых и четыре последних столбца устроены несколько иначе, чем остальные).
Ответ
2005004.
