Задача 78685

Темы:    [ Числовые таблицы и их свойства ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 3+ Классы: 10,11

Условие

В таблице A размером 10×10 написаны какие-то числа. Обозначим сумму всех чисел в первой строке через s₁, во второй – через s₂ и т.д. Аналогично сумму чисел в первом столбце обозначим через t₁, во втором – t₂ и т.д. Составлена новая таблица B размером 10×10, в неё вписаны числа следующим образом: в первой клетке первой строки пишется наименьшее из чисел s₁ и t₁, в третьей клетке пятой строки пишется наименьшее из чисел s₅ и t₃, аналогично записана вся таблица. Оказалось, что можно так занумеровать клетки таблицы B числами от 1 до 100, что в клетке с k-м номером будет стоять число, меньшее или равное k. Какое максимальное значение может принимать при этих условиях сумма всех чисел таблицы A?

Решение

  Пример таблицы A, для которой сумма всех чисел равна 955.

  Таблица B в этом случае совпадает с A.
  Оценка. Перенумеровав столбцы и строки и, возможно, отразив таблицу относительно диагонали, сделаем так, что t₁₀ – наибольшее из чисел s₁, ..., s₁₀, t₁, ..., t₁₀. Тогда в десятом столбце стоят числа s₁, ..., s₁₀. Сумма чисел в этих клетках не превосходит суммы номеров клеток, в которых они стоят, а значит, не больше чем  91 + ... + 100 = 955.  С другой стороны, эта сумма равна сумме всех чисел таблицы A. Следовательно, сумма всех чисел таблицы A не превосходит 955.

Ответ

955.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	31
Год	1968
вариант
	1
Класс	10
Тур	2
задача
Номер	2