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

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

Условие

Автор: Тупанов А.

В таблицу n×n записаны n² чисел, сумма которых неотрицательна. Докажите, что можно переставить столбцы таблицы так, что сумма n чисел по диагонали, идущей из левого нижнего угла в правый верхний, будет неотрицательна.


Решение

  Назовем циклическим сдвигом такое преобразование таблицы: 1-й столбец переставляется на место 2-го, 2-й на место 3-го, ..., наконец последний, n-й – на место 1-го. Обозначим через s0 сумму чисел, стоящих на диагонали таблицы, через sk – сумму чисел, которые попадут на диагональ, если проделать циклический сдвиг k раз. Сумма s всех чисел в таблице равна  s0 + s1 + ... + sn–1,  потому что если проделать циклический сдвиг 0, 1, ...,  n – 1  раз, то за это время каждое число в таблице побывает на диагонали ровно однажды.
  По условию s неотрицательно, следовательно, некоторое sk должно быть неотрицательно. Проделав циклический сдвиг k раз, мы получим требуемую перестановку столбцов.

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

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

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

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