Клетки бесконечного клетчатого листа бумаги красятся в k цветов (каждая клетка красится целиком в один цвет). При каком наибольшем k в каждом клетчатом прямоугольнике со сторонами 3 и 4 встретятся клетки всех этих цветов?
Разобьем бесконечный клетчатый лист бумаги на десятиклеточные фигурки (см. верхний рис.) так, как показано на среднем рисунке.
Требуемая раскраска в 10 цветов получится, если раскрасить одну такую фигуру в 10 цветов, а остальные раскрасить ровно таким же способом.
Очевидно, что более чем в 12 цветов требуемым образом покрасить лист нельзя. Пусть есть раскраска в 11 или 12 цветов. Предположим, что нашлась такая раскраска в 11 цветов, что в каждом квадрате 3 × 3 все цвета различны. Рассмотрим один такой квадрат. В содержащем его прямоугольнике 3 × 4 имеется лишь 11 различных цветов. Поэтому в дополнительной полоске 3 × 1 какие-то два цвета совпадают. Тогда в квадрате 3 × 3, содержащем эту полоску, какие-то два цвета совпадают.
Пусть у нас есть раскраска в n цветов, где n равно 11 или 12. Выберем квадрат в котором не более разных цветов. Достроим его до прямоугольников 3 × 4 и 4 × 4 так, как показано на нижнем рисунке. Тогда в полосках 3 × 1 и 1 × 3 представлены одинаковые тройки цветов. Накроем горизонтальным прямоугольником 3 × 4 клетку, помеченную крестиком. Тогда этот прямоугольник будет содержать 5 клеток из полосок, значит, в нем имеется не менее двух пар клеток одного цвета, поэтому общее количество цветов не превосходит 10. Противоречие.
Ответ: 10.