Каждая точка плоскости, имеющая целочисленные координаты, 
 раскрашена в один из n цветов. 
 Докажите, что найдется прямоугольник с вершинами в точках 
 одного цвета.


			
Рассмотрим полосу из n+1 подряд идущих горизонтальных рядов точек. 
 Рассмотрим вертикальные ряды этой полосы, состоящие из n+1 точек.  
 Существует лишь конечное число способов 
 раскрасить в n цветов n+1 точек (первую точку можно раскрасить 
 n способами, независимо от этого вторую точку также можно  
 окрасить n способами, и т.д., всего имеется 
 nn+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' являются вершинами прямоугольника 
 и имеют один и тот же цвет, т.е. образуют искомую четверку точек.
Принцип Дирихле (прочее) Раскраски