Задача 60365

Темы:    [ Раскраски ] [ Принцип Дирихле (прочее) ]

Сложность: 3+ Классы: 7,8,9

Условие

Бесконечная клетчатая доска раскрашена в три цвета (каждая клеточка – в один из цветов).
Докажите, что найдутся четыре клеточки одного цвета, расположенные в вершинах прямоугольника со сторонами, параллельными стороне одной клеточки.

Подсказка

Пусть доска раскрашена в два цвета. Рассмотрим произвольный столбец. Один из цветов встречается в нем бесконечное число раз. Зафиксируем этот цвет. Вычеркнем из таблицы все строчки, которые в выбранном столбце не содержат фиксированный цвет. Покажите, что в оставшейся таблице можно найти четыре нужные клетки. Для решения задачи с произвольным числом цветов, примените индукцию.