2014-06-08
На плоскости с прямоугольной системой координат рассматривается множество М точек $(x, y)$, где $x, y \in \mathbf{N}$, причем $x \leq 12, y \leq 12$. Каждая из этих 144 точек окрашена либо в красный, либо в белый, либо в синий цвет. Доказать, что существует прямоугольник (со сторонами, параллельными осям), все вершины которого принадлежат множеству М и одинаково окрашены.
Решение:
Естественным образом разобьем все точки из М на 12 строк (по первой координате) и на 12 столбцов (по второй координате). Существует цвет, в который окрашено не менее 144/3 = 48 точек. Выберем из них ровно 48 точек. Число выбранных точек в столбце со второй координатой, равной $1, 2, \cdots, 12$, обозначим через $a_{1}, a_{2}, \cdots, a_{12}$ соответственно $(a_{1} + a_ {2} + \cdots + a_{12} = 48)$. Тогда количество пар выбранных точек в i-м столбце равно $a_{i}(a_{i} - 1)/2$, а общее количество пар точек, у которых вторые координаты совпадают, равно
$A = \frac{ a_{1}(a_{1} - 1)}{2} + \frac{a_{2}(a_{2} - 1)}{2} + \cdots + \frac{a_{12}(a_{12} - 1)}{2} = \frac{1}{2} (a_{1}^{2} + \cdots + a_{12}^{2}) - \frac{1}{2}(a_{1} + \cdots + a_{12})$.
Пользуясь теоремой о средних, получаем оценку
$A \geq \frac{1}{2} \frac{(a_{1} + \cdots + a_{12})^{2}}{12} - \frac{1}{2}(a_{1} + \cdots + a_{12}) = \frac{1}{2} \cdots \frac{48^{2}}{12} - \frac{1}{2} \cdots 48 = 72$
Каждой паре выбранных точек, лежащих в одном столбце, соответствует пара строк, в которых эти точки находятся. Поскольку количество различных пар строк, равное $C_{12}^{2} = 66$, меньше числа A, то найдутся две пары выбранных точек, которым соответствует одна и та же пара строк. Найденные 4 точки являются вершинами искомого прямоугольника.