Клетки прямоугольника 5×41 раскрашены в два цвета. Докажите, что можно выбрать три строки и три столбца так, что все 9 клеток, стоящие на их пересечениях, покрашены в один цвет.

Доказательство данного утверждения можно провести с помощью принципа Дирихле.

Рассмотрим прямоугольник размером 5×41 с клетками, раскрашенными в два цвета. Пусть каждая строка рассматривается как набор цветов в клетках этой строки (например, цвет 1 и цвет 2).

Если в одной из строк есть 3 клетки одного цвета, то мы можем выбрать эту строку в качестве первой строки для нашего выбора. Тогда из оставшихся 4 строк нам нужно выбрать еще две строки таким образом, чтобы в каждом столбце выбранных строк было по клетке того же цвета, что и в первой строке. Это всегда возможно, так как в каждом столбце есть две клетки, и мы выбираем две строки, чтобы покрыть все возможные комбинации цветов в каждом столбце.

Если во всех строках есть не более 2 клеток одного цвета, то мы можем выбрать любые три строки, и в каждом столбце будет не менее двух клеток одного цвета. В этом случае мы также можем выбрать три столбца таким образом, чтобы в каждом из них было не менее двух клеток одного цвета.

Таким образом, в любом случае мы можем выбрать три строки и три столбца так, что все 9 клеток, стоящие на их пересечениях, будут покрашены в один цвет.