Условие
Каждая точка плоскости, имеющая целочисленные координаты,
раскрашена в один из n цветов.
Докажите, что найдется прямоугольник с вершинами в точках
одного цвета.
Подсказка
Рассмотрим целые точки, расположенные в бесконечной
горизонтальной полосе. В этой полосе найдутся два одинаково
окрашенных вертикальных ряда точек.
Решение
Рассмотрим полосу из n+1 подряд идущих горизонтальных рядов точек.
Рассмотрим вертикальные ряды этой полосы, состоящие из n+1 точек.
Существует лишь конечное число способов
раскрасить в n цветов n+1 точек (первую точку можно раскрасить
n способами, независимо от этого вторую точку также можно
окрасить n способами, и т.д., всего имеется
n
n+1 способов раскраски n+1 точек в n цветов).
Поэтому среди вертикальных рядов рассматриваемой полосы (этих рядов
бесконечно много) найдутся два одинаково окрашенных ряда A и B,
т.е. таких ряда, что точки этих рядов,
расположенные в i-ом горизонтальном ряду (i=1,2,...,n+1),
имеют один и тот же цвет.
Поскольку в вертикальном ряду A n+1 целая точка, в нем найдутся две
точки X и Y одного цвета. В ряду B две точки X', Y', раcположенные
в тех же горизонтальных рядах, что и точки X и Y, окрашены тем же
цветом, что и X, Y (так как ряды A и B одинаково окрашены).
Точки X, Y, X', Y' являются вершинами прямоугольника
и имеют один и тот же цвет, т.е. образуют искомую четверку точек.
Источники и прецеденты использования
