|
|
 |
Условие
Даны две таблицы 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. Идея другого решения. Заменим в таблицах единицы кубиками (а нули – пустотами). По условию кубики образуют ступенчатую стенку (ступени идут из левого нижнего угла в правый верхний. Если в верхнем слое стенки А кубиков больше, чем в В, сдвинем крайний левый кубик этого слоя влево, пока он не упадёт вниз (см. рис). Нетрудно проверить, что при этом условие на суммы чисел в верхних строках не нарушается.
2. Для знатоков. Ясно, что "ступенчатые стенки" – это повернутые на 180° диаграммы Юнга. Обозначим через CT диаграмму, полученную из C переворотом. Мы фактически доказали следующий факт: если в диаграммах Юнга A и B квадратиков поровну, и B мажорирует A, то AT мажорирует BT.
3. 5 баллов.
