ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73704
Темы:    [ Числовые таблицы и их свойства ]
[ Упорядочивание по возрастанию (убыванию) ]
[ Принцип Дирихле (прочее) ]
[ Мощность множества. Взаимно-однозначные отображения ]
Сложность: 3+
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

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


Решение

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

  Оценка. Пусть  a1, a2, ..., an  – числа k-го столбца, занумерованные в порядке возрастания:  a1 < a2 < ... < an.  Рассмотрим числа, стоящие в тех же строках, где стоят  a1, a2, ..., ai,  и в первых k столбцах. Эти ki чисел не превосходят ai, поэтому  ai   kii = 1, 2, ..., n,  получим
a1 + a2 + ... + an ≥ ½ 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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .