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

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

Условие

Даны две таблицы A и B, в каждой m строк и n столбцов. В каждой клетке каждой таблицы записано одно из чисел 0 или 1, причём в строках таблиц числа не убывают (при движении по строке слева направо), и в столбцах таблиц числа не убывают (при движении по столбцу сверху вниз). Известно, что при любом k от 1 до m сумма чисел в верхних k строках таблицы A не меньше суммы чисел в верхних k строках таблицы B. Известно также, что всего в таблице A столько же единиц, сколько в таблице B. Докажите, что при любом l от 1 до n сумма чисел в левых l столбцах таблицы A не больше суммы чисел в левых l столбцах таблицы B.


Решение

Предположим противное. Рассмотрим наименьшее l, при котором сумма l левых столбцов A превзошла аналогичную сумму B. Тогда в l-м столбце число нулей в A (обозначим его k) меньше, чем в B. Разрежем каждую из таблиц двумя перпендикулярными прямыми на 4 прямоугольные части (угла), отделив l столбцов слева и k строк сверху (см. рис. для таблицы A, где "зона единиц" показана темным). Сравним суммы в углах. В левых верхних углах обеих таблиц единиц, очевидно, нет. Поэтому сумма в левом нижнем углу равна сумме в l левых столбцах, и у A она больше по построению. Аналогично сумма в правом верхнем углу равна сумме в k верхних строках, и у A она не меньше по условию. Наконец, правый нижний угол A целиком заполнен единицами, поэтому сумма там не меньше. В итоге в А единиц оказывается больше, чем в B. Противоречие.

Замечания

  1. Идея другого решения. Заменим в таблицах единицы кубиками (а нули – пустотами). По условию кубики образуют ступенчатую стенку (ступени идут из левого нижнего угла в правый верхний. Если в верхнем слое стенки А кубиков больше, чем в В, сдвинем крайний левый кубик этого слоя влево, пока он не упадёт вниз (см. рис). Нетрудно проверить, что при этом условие на суммы чисел в верхних строках не нарушается.

  Так будем поступать до тех пор, пока верхний слой стенки А не сравняется с верхним слоем стенки В. Затем возьмёмся за второй слой и т. д. В конце концов А превратится в В. Но на каждом шаге количество кубиков в левых l столбцах A не уменьшалось.

  2. Для знатоков. Ясно, что "ступенчатые стенки" – это повернутые на 180° диаграммы Юнга. Обозначим через CT диаграмму, полученную из C переворотом. Мы фактически доказали следующий факт: если в диаграммах Юнга A и B квадратиков поровну, и B мажорирует A, то AT мажорирует BT.

  3. 5 баллов.

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

олимпиада
Название Турнир городов
Турнир
Дата 2000/2001
Номер 22
вариант
Вариант весенний тур, основной вариант, 10-11 класс
Задача
Номер 4

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

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