Задача 73704

Темы:    [ Числовые таблицы и их свойства ] [ Упорядочивание по возрастанию (убыванию) ] [ Принцип Дирихле (прочее) ] [ Мощность множества. Взаимно-однозначные отображения ]

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

Условие

Автор: Васильев Н.Б.

Пусть k и n – натуральные числа,  k ≤ n.  Расставьте первые n² натуральных чисел в таблицу n×n так, чтобы в каждой строке числа шли в порядке возрастания и при этом сумма чисел в k-м столбце была  а) наименьшей;  б) наибольшей.

Решение

  а) Пример. Если расставить числа так, как показано в таблице, – сначала заполнить первые k столбцов, строку за строкой, числами от 1 до kn, а затем оставшимися числами заполнить последние  n – k  столбцов (как угодно, лишь бы выполнялось условие возрастания чисел в каждой строке) – то сумма чисел в k-м столбце будет равна  ½ kn(n + 1).

  Оценка. Пусть  a₁, a₂, ..., a_n  – числа k-го столбца, занумерованные в порядке возрастания:  a₁ < a₂ < ... < a_n.  Рассмотрим числа, стоящие в тех же строках, где стоят  a₁, a₂, ..., a_i,  и в первых k столбцах. Эти ki чисел не превосходят a_i, поэтому  a_i   k_ii = 1, 2, ..., n,  получим
a₁ + a₂ + ... + a_n ≥ ½ kn(n + 1).

  б) Заменим в таблице каждое число a на  (n² + 1 – a)  и затем переставим числа в каждой строке в обратном порядке. Ясно, что это – взаимно однозначное преобразование множества таблиц из чисел 1, 2, ..., n², удовлетворяющих условию задачи. При этом преобразовании каждое число в k-м столбце новой таблицы A'  равно числу в той же строке и в (n+1–k)-м столбце старой таблицы A; поэтому сумма чисел в k-м столбце таблицы A'  равна  n(n² + 1) – S,  где S – сумма чисел в  (n+1–k)-м столбце A. Так что достаточно решить задачу а) для столбца с номером  n + 1 – k.  Следовательно, максимальная сумма в k-м столбце равна  n(n² + 1) – ½ (n + 1 – k)n(n + 1) = ½ n((n – 1)² + k(n + 1)).

Ответ

а)  ½ kn(n + 1);   б)  ½ n((n – 1)² + k(n + 1)).

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

журнал
Название	"Квант"
год
Год	1972
выпуск
Номер	10
Задача
Номер	М169