4 votos

Conjuntos óptimos para el problema de coloreado de planos

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 {0,1,,k}×{0,,k2(k+1)2}{0,1,,k}×{0,,k2(k+1)2} . De cada fila {0,,k}×{j}{0,,k}×{j} elige un par (aj,j),(bj,j)(aj,j),(bj,j) con aj<bjaj<bj de puntos que son del mismo color, que debe existir por encasillamiento. Puesto que sólo hay k(k+1)2k(k+1)2 posibles opciones para (aj,bj)(aj,bj) para algún par (a,b)(a,b) hay al menos k+1k+1 valores de jj tal que (a,b)=(aj,bj)(a,b)=(aj,bj) . Dado que existen kk colores, algún par (j1,j2)(j1,j2) de valores distintos de jj entre ellos han (a,j1)(a,j1) y (a,j2)(a,j2) del mismo color, y el rectángulo deseado tiene el conjunto de vértices {a,b}×{j1,j2}{a,b}×{j1,j2} .

Esto en realidad demuestra algo más fuerte, a saber, que hay un conjunto de k42+k3+k22+k+1k42+k3+k22+k+1 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 k2(k+1)2k2(k+1)2 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 O(k4)O(k4) ? Más explícitamente, ¿existen conjuntos, de tamaño o(k4)o(k4) tal que para cualquier coloración del plano con kk colores, el kk -¿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?

2voto

JiminyCricket Puntos 143

Puedes conseguir O(k3)O(k3) con el mismo método utilizando más de k+1k+1 puntos por fila. Una fila de k+xk+x puntos deben contener al menos xx pares de colores idénticos, por lo que nn dichas filas contienen nxnx estos pares. En filas de k+xk+x puntos, hay (k+x)(k+x1)/2(k+x)(k+x1)/2 diferentes posiciones de pareja, y cada una puede colorearse con kk colores. Por lo tanto, se garantiza que dos pares en la misma posición tienen los mismos colores si nx>k(k+x)(k+x1)/2nx>k(k+x)(k+x1)/2 . En n=k(k+x)(k+x1)/(2x)n=k(k+x)(k+x1)/(2x) el número total n(k+x)n(k+x) de puntos es k(k+x)2(k+x1)/(2x)k(k+x)2(k+x1)/(2x) y minimizarlo con respecto a xx para grandes kk produce x=k/2+O(1)x=k/2+O(1) por lo que el número mínimo de puntos necesarios es (32k)3+O(k2)(32k)3+O(k2) .

Sospecho que será difícil hacerlo mucho mejor, pero no sé cómo demostrarlo.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X