Областная олимпиада по математике 2000 года за 9 класс | Казахстанские олимпиады

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