Областная олимпиада по математике, 2000 год, 9 класс

На доске размером $1999\times 1999$ покрашено несколько квадратиков $1\times 1$ так, что на любой строке и на любом столбце имеется ровно один закрашенный квадратик. Докажите, что каждый квадрат $1000 \times 1000$ (на этой доске) содержит хотя бы одну закрашенную клетку.

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

Из условия понятно что всего на доске 1999 закрашенных клеток.Предположим что все же нашлось такой квадрат 1000$\times$1000 что в ней нету ни одной закрашенной клетки. В этом случае каждому столбцу и строке приходится по одной закрашенной клетке вне этого квадрата.То есть понадобится нам для этого 2000 закрашенных клеток. Но их у нас 1999. Противоречие.