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

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

Условие

а) В таблицу 2×n (где  n > 2)  вписаны числа. Суммы во всех столбцах различны. Докажите, что можно переставить числа в таблице так, чтобы суммы в столбцах были различны и суммы в строках были различны.
б) В таблицу 10×10 вписаны числа. Суммы во всех столбцах различны. Всегда ли можно переставить числа в таблице так, чтобы суммы в столбцах были различны и суммы в строках были различны?


Решение

  а) Допустим, суммы в строках равны. Если есть столбец, где числа различны, то поменяем их местами, и суммы чисел в строках станут разными. Если в каждом столбце оба числа равны, то все числа в строке различны. Возьмём три наименьших числа  a < b < c  в верхней строке и переставим их циклически. Так как
b + a < a + c < b + c,  причём  b + c  меньше суммы чисел в любом из оставшихся  n – 3  столбцов, то суммы чисел в столбцах останутся различными. Теперь у нас есть столбец, где числа различны.

  б) Приведём контрпример для таблицы n×n. Впишем в столбцы последовательно по  0, 1, ...,  n – 2,  n  единиц, а в остальные клетки впишем нули. Число, равное
0 + 1 + … + (n – 2) + n,  нельзя по-другому разбить на n целых различных неотрицательных слагаемых. Следовательно, указанное разбиение единиц по столбцам единственное, при котором суммы в них различны. Значит, при любой "допустимой" перестановке обязательно должны быть столбец из нулей и столбец из единиц. То же самое можно сказать и про строки, если суммы в них различны. Но наличие столбца из нулей противоречит наличию строки из единиц.


Ответ

б) Не всегда.

Замечания

Баллы: 3 + 6

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

олимпиада
Название Турнир городов
Турнир
Номер 36
Дата 2014/15
вариант
Вариант весенний тур, сложный вариант, 8-9 класс
задача
Номер 5

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

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