Existe un problema razonablemente conocido:
Dado un plano con cada punto coloreado de uno de k colores, demuestre que existe un rectángulo cuyos vértices son todos del mismo color, cuyos ejes son paralelos a los ejes x e y
Una solución a este problema es considerar puntos en . De cada fila elige un par con de puntos que son del mismo color, que debe existir por encasillamiento. Puesto que sólo hay posibles opciones para para algún par hay al menos valores de tal que . Dado que existen colores, algún par de valores distintos de entre ellos han y del mismo color, y el rectángulo deseado tiene el conjunto de vértices .
Esto en realidad demuestra algo más fuerte, a saber, que hay un conjunto de puntos que deben contener vértices de un rectángulo, orientados con los ejes de coordenadas, que son todos del mismo color. También está bastante claro que el no se puede mejorar con este método.
Por otro lado, el método parece ineficiente, al menos para k grandes. Así que mi pregunta es: ¿Se puede hacer algo mejor que ? Más explícitamente, ¿existen conjuntos, de tamaño tal que para cualquier coloración del plano con colores, el -¿el enésimo de estos conjuntos debe contener los vértices, todos del mismo color, de un rectángulo cuyos lados sean paralelos a los ejes de coordenadas? En caso afirmativo, ¿cuál es el mejor número (conocido) de puntos?