Разделы 
Дополнительно
Задача по математике - 2024
2019-01-23 
В прямоугольной таблице 9 строк и 2004 столбца. В ее клетках расставлены числа от 1 до 2004, каждое - по 9 раз. При этом в любом столбце числа различаются не более, чем на 3. Найдите минимальную возможную сумму чисел в первой строке.
Решение:
Докажем, что сумма не может быть меньше. Переставив, если нужно, столбцы, будем далее считать, что числа в первой строке стоят в неубывающем порядке. Пусть $a_i - i$-е число первой строки. Рассмотрим сумму
$S = (a_1 - 1) + (a_2 - 1) + (a_3 - 1) + (a_4 - 2) + \cdots + (a_i - (i - 2)) + \cdots + (a_{2003} - 2001) + (a_{2004} - 2001)$.
Заметим, что сумма вычитаемых чисел как раз равна $\frac{2003 \cdot 2002}{2} + 1$; поэтому достаточно доказать, что $S \geq 0$. Обозначим $i$-е слагаемое в нашей сумме через $d_i$. Если в этой сумме нет отрицательных членов, все очевидно. Ясно, что $а_{2004} \geq 2001, а_2 \geq a_1 \geq 1$, т. е. $d_1, d_2, d_{2004} \geq 0$.
Пусть $d_i < 0$, т. е. $a_i \leq i - 3$. Тогда в $i$ первых столбцах содержатся только числа от 1 до $i$, следовательно, там содержатся все такие числа. Отсюда следует, что $a_i = i - 3, a_{i+1} \geq i +1,$ и $d_i + d_{i+1} \geq 0$. Таким образом, для любого отрицательного $d_i$ сумма его со следующим членом положительна, поэтому, объединив такие слагаемые в пары, получаем сумму неотрицательных слагаемых, что и требовалось.
Осталось привести пример таблицы, для которой оценка достигается:
(два первых и четыре последних столбца устроены несколько иначе, чем остальные).
Ответ. $\frac{2003 \cdot 2002}{2} + 1 = 2005004$.
В прямоугольной таблице 9 строк и 2004 столбца. В ее клетках расставлены числа от 1 до 2004, каждое - по 9 раз. При этом в любом столбце числа различаются не более, чем на 3. Найдите минимальную возможную сумму чисел в первой строке.
Решение:
Докажем, что сумма не может быть меньше. Переставив, если нужно, столбцы, будем далее считать, что числа в первой строке стоят в неубывающем порядке. Пусть $a_i - i$-е число первой строки. Рассмотрим сумму
$S = (a_1 - 1) + (a_2 - 1) + (a_3 - 1) + (a_4 - 2) + \cdots + (a_i - (i - 2)) + \cdots + (a_{2003} - 2001) + (a_{2004} - 2001)$.
Заметим, что сумма вычитаемых чисел как раз равна $\frac{2003 \cdot 2002}{2} + 1$; поэтому достаточно доказать, что $S \geq 0$. Обозначим $i$-е слагаемое в нашей сумме через $d_i$. Если в этой сумме нет отрицательных членов, все очевидно. Ясно, что $а_{2004} \geq 2001, а_2 \geq a_1 \geq 1$, т. е. $d_1, d_2, d_{2004} \geq 0$.
Пусть $d_i < 0$, т. е. $a_i \leq i - 3$. Тогда в $i$ первых столбцах содержатся только числа от 1 до $i$, следовательно, там содержатся все такие числа. Отсюда следует, что $a_i = i - 3, a_{i+1} \geq i +1,$ и $d_i + d_{i+1} \geq 0$. Таким образом, для любого отрицательного $d_i$ сумма его со следующим членом положительна, поэтому, объединив такие слагаемые в пары, получаем сумму неотрицательных слагаемых, что и требовалось.
Осталось привести пример таблицы, для которой оценка достигается:
(два первых и четыре последних столбца устроены несколько иначе, чем остальные).
Ответ. $\frac{2003 \cdot 2002}{2} + 1 = 2005004$.
