Олимпиада имени Леонарда Эйлера2011-2012 учебный год, I тур заключительного этапа

В каждую клетку таблицы $2012 \times 2012$ вписан либо нуль, либо единица, причем в каждом столбце и каждой строке есть как нули, так и единицы. Докажите, что в этой таблице найдутся две строки и два столбца такие, что на концах одной из диагоналей образованного ими прямоугольника стоят нули, а другой — единицы. ( И. Рубанов, методкомиссия )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Решение. Рассмотрим строку $C_1$, в которой больше всего единиц. В ней есть клетка $X$, в которой стоит нуль, а в столбце, где стоит клетка $X$ — клетка $Y$, в которой стоит единица. Если в строке $C_2$, где стоит клетка $Y$, под какой-то единицей строки $C_1$ стоит нуль, то все доказано: искомыми строками будут $C_1$ и $C_2$, а столбцами — тот, где стоят клетки $X$ и $Y$, и тот, где под единицей в $C_1$ стоит нуль в $C_2$. Если же под каждой единицей строки $C_1$ в строке $C_2$ тоже стоит единица, то в строке $C_2$ больше единиц, чем в строке $C_1$, что противоречит выбору строки $C_1$.