|
|
 |
Условие
В клетках таблицы 15×15 изначально записаны нули. За один ход разрешается выбрать любой её столбец или любую строку, стереть записанные там числа и записать туда все числа от 1 до 15 в произвольном порядке – по одному в каждую клетку. Какую максимальную сумму чисел в таблице можно получить такими ходами?
Решение 1
Лемма. Пусть k – натуральное число. В прямоугольнике m×n (m, n ≥ k) изначально все клетки белые. За один ход можно выбрать ряд (строку или столбец), и перекрасить клетки этого ряда так, чтобы в нём оказалось не более k чёрных клеток (остальные клетки белые). Тогда в любой момент в прямоугольнике не менее (m – k)(n – k) белых клеток.
Доказательство. Индукция по числу клеток в прямоугольнике.
База. Если m = k или n = k, утверждение очевидно.
Шаг индукции. Пусть m, n > k. Рассмотрим ситуацию после нескольких перекрашиваний. Пусть, для определенности, последней перекрашивалась некоторая строка; тогда в этой строке не менее n – k белых клеток. Исключив из рассмотрения эту строку, можно считать, что все перекрашивания, кроме последнего, происходили в прямоугольнике (m–1)×n. По предположению индукции в этом прямоугольнике не менее (m – 1 – k)(n – k) белых клеток. Итого, в прямоугольнике m×n не менее (n – k) + (m – 1 – k)(n – k) = (m – k)(n – k) белых клеток.
Оценка. Положим n = m = 15. Пусть после нескольких ходов в таблице стоит ai чисел, равных i (1 ≤ i ≤ 15). Применим лемму, считая чёрными клетки с числом 15. При этом k = 1, и значит, a15 ≤ 15² – 14². Далее применим лемму, считая чёрными клетки с числами 15 и 14. При этом k = 2, поэтому a15 + a14 ≤ 15² – 13². Рассуждаем так далее, применяя лемму, считая чёрными клетки с числами 15, 14, ... , s + 1 (s = 14, 13, ..., 0). При этом k = 15 – s, поэтому a15 + ... + as+1 ≤ 15² – s². Складывая все эти неравенства, получаем
15a15 + 14a14 + 13a13 + ... + 2a2 + a1 ≤ 15·15² – (14² + ... + 0²) = 2360.
Слева в этом неравенстве стоит сумма всех чисел в таблице.
Пример. Числа будем записывать в порядке убывания: в столбцах – сверху вниз, в строках – слева направо. Будем последовательно изменять первый (слева) столбец, первую (сверху) строку, второй столбец, вторую строку, ..., 15-й столбец, 15-ю строку. Тогда в первой строке и первом
столбце будут стоять числа 15, в остальных клетках второй строки и второго столбца – 14 и т.д., то есть все неравенства из предыдущего рассуждения обратятся в равенства.
Решение 2
Будем называть столбцы и строки линиями.
Рассмотрим алгоритм расстановки чисел, дающий максимальную возможную сумму. Мы немного упростим этот алгоритм; при этом сумма всех чисел не уменьшится – то есть он останется оптимальным.
Заметим, что делать два хода в одну и ту же линию не имеет смысла – второй ход уничтожает все числа, появившиеся в результате первого; поэтому первого хода можно просто не делать. Далее, если в какую-то линию не было хода, то можно было сделать произвольный ход в неё перед всеми остальными
ходами – сумма чисел от этого не уменьшится. Таким образом, можно считать, что в каждую линию был сделан ровно один ход. Переставим строки таблицы так, чтобы первый горизонтальный ход был в первую (верхнюю) строку,
второй – во вторую и т.д. Аналогично можно считать, что столбцы, в которые делаются вертикальные ходы, идут слева направо.
Назовём вкладом некоторого хода сумму чисел, поставленных на доску во время него и впоследствии не стёртых. Тогда ясно, что сумма всех чисел таблицы – это сумма вкладов всех ходов.
Рассмотрим некоторый вертикальный ход. Заменим порядок чисел в нём на
убывающий порядок сверху вниз. Тогда вклад этого хода не уменьшился, так как не будут стёрты ровно несколько верхних чисел этого столбца, а их сумма в новой расстановке – максимальная возможная. Итак, можно считать, что при каждом вертикальном ходе числа расставлялись по убыванию сверху вниз.
Аналогично при каждом ходе в строку числа можно расставлять по убыванию слева направо. Таким образом, за все ходы в каждую клетку будут поставлены два числа – её номер справа в строке и её номер снизу в столбце. Тогда в этой клетке будет стоять не больше, чем максимальное из этих чисел.
В примере из решения 1 ровно так и происходит, поэтому он и даёт максимальную сумму.
Ответ
2360.
