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

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

Условие

Автор: Bapat R.B.

В каждой клетке квадратной таблицы написано по числу. Известно, что в каждой строке таблицы сумма двух наибольших чисел равна a,
а в каждом столбце сумма двух наибольших чисел равна b. Докажите, что  a = b.


Решение 1

Пусть в таблице n строк. Возьмём в каждой строке по два наибольших числа и выпишем эти 2n чисел в порядке возрастания. Ввиду равенства сумм в пары входят первое и последнее, второе и предпоследнее и т.д. Отметим в таблице  n + 1  наибольших из выписанных чисел. По принципу Дирихле найдутся два отмеченных числа в одном столбце; их сумму обозначим через s. По условию,  s ≤ b.  С другой стороны, s не меньше суммы двух наименьших из отмеченных чисел, а это как раз центральная пара из выписанных чисел, и её сумма равна a. Значит,  a ≤ s ≤ b.  Аналогично доказывается, что  b ≤ a.


Решение 2

Пусть  a > b.  Числа в таблице, не меньшие a/2,  назовём большими. В каждом столбце не больше одного большого числа. В каждой строке не меньше одного большого числа. Значит, всего в таблице не больше и не меньше чем n больших чисел, то есть их ровно n, причём в каждой строке и в каждом столбце – ровно по одному. Пусть x – наименьшее большое число. В его строке найдётся число  a – x,  которое не является большим. В столбце последнего найдётся большое число, оно не меньше x. Мы нашли столбец и два числа в нём, сумма которых не меньше a, то есть больше b. Противоречие.

Замечания

Баллы: 8-9 кл. – 10, 10-11 кл. – 8

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

олимпиада
Название Московская математическая олимпиада
год
Год 2011
Номер 74
класс
Класс 8
задача
Номер 6
олимпиада
Название Турнир городов
Турнир
Дата 2010/2011
Номер 32
вариант
Вариант весенний тур, сложный вариант, 8-9 класс
Задача
Номер 7
олимпиада
Название Турнир городов
Турнир
Дата 2010/2011
Номер 32
вариант
Вариант весенний тур, сложный вариант, 10-11 класс
Задача
Номер 6

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

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