|
|
 |
Условие
Каждая точка плоскости, имеющая целочисленные координаты,
раскрашена в один из $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'$ являются вершинами прямоугольника и имеют один и тот же цвет, т.е. образуют искомую четверку точек.
Источники и прецеденты использования
| web-сайт | |
| задача |
