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