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