Целочисленная матрица

[Ktina]

Дана матрица $m\times n$, причём $n>m$, элементами которой являются целые числа.
Известно, что в каждом столбце стоит хотя бы один нуль.

Обязательно ли найдётся такой нуль, что с ним в одной строчке стоит больше нулей, чем с ним в одном столбце?

[TOTAL]

Пока удалю.

[Dave]

Ответ: обязательно.

Доказательство. Допустим противное - в столбце любого нуля всего нулей не меньше, чем в его строке. Переставим столбцы и строки так, что количества нулей в них идут по возрастанию, т.е. если в $i$-м столбце, $i=\overline{1,n}$ всего $a_i$ нулей, а в $j$-й строке, $j=\overline{1,m}$ всего $b_j$ нулей, то $a_1 \leqslant a_2 \leqslant \ldots \leqslant a_n$ и $b_1 \leqslant b_2 \leqslant \ldots \leqslant b_m$. Все условия задачи и наше предположение остались верными после перестановки.
Докажем по индукции, что $a_i \geqslant b_i$ для любого $i=\overline{1,m}$.
В первом столбце есть хотя бы один нуль, пусть он находится в $j$-й строке. По предположению, $a_1 \geqslant b_j$. Но $b_j \geqslant b_1$, значит $a_1 \geqslant b_1$.
Пусть утверждение верно при всех $i \leqslant k$, $k \in \mathbb N$. Если существует хотя бы один нуль, номер столбца $p$ и номер строки $q$ которого удовлетворяют одновременно условиям $p \leqslant k+1$ и $q \geqslant k+1$, то $a_{k+1} \geqslant a_p \geqslant b_q \geqslant b_{k+1}$. Если же таких нулей нет, то, посчитав общее количество нулей, находящихся на пересечении первых $k+1$ столбцов и первых $k$ строк мы получим, что, с одной стороны, оно не меньше, чем $a_1+\ldots+a_{k+1} \geqslant a_1+\ldots+a_k+1$, ибо все нули в этих столбцах сосредоточены в первых $k$ строках, а, с другой стороны, это количество не больше, чем $b_1+\ldots+b_k$, что, по индукционному предположению, не больше $a_1+\ldots+a_k$ - противоречие.
Утверждение о $a_i \geqslant b_i$ доказано. Теперь уже легко получить противоречие с основным предположением. Посчитаем аналогичным образом общее количество нулей в матрице. Т.к. $n>m$ и в столбцах c номерами, большими чем $m$, есть минимум по одному нулю, то это количество не меньше $a_1+\ldots+a_m+1 \geqslant b_1+\ldots+b_m+1$. Но оно также равно $b_1+\ldots+b_m$ - противоречие.

[Dave]

А с какой олимпиады эта задача?

[Ktina]

Dave в сообщении #576673 писал(а):

А с какой олимпиады эта задача?

Вот ссылка: http://ri.kharkov.ua/olympiad/Otbor2009_tur3.pdf
Задача № 3 для 9-го класса.