Me encontré con este obstáculo en un problema de análisis armónico; sé epsilon sobre problemas de coloración.
¿Es posible colorear finitamente Z^2 de modo que los puntos (x,a) y (a,y) tengan colores diferentes para cada x, y y a en los números enteros (exceptuando, por supuesto, los casos triviales x=y=a)?
No, esto no es posible. En primer lugar, hay que tener en cuenta que la pregunta es la misma si sustituimos Z por cualquier subconjunto infinito de Z. Ahora, supongamos que fuera posible colorear Z 2 con k colores, donde k es el mínimo. Escoge cualquier fila r. Podemos encontrar un conjunto infinito S de enteros que no contenga r tal que para x en S, todos los (x, r) tengan el mismo color c. Ningún punto en SxS puede tener color c, así que SxS está coloreado con k-1 colores. Pero esto contradice la minimidad de k.
No.
Supongamos que esto fuera posible. Para z \in Z, dejemos que R z sean los colores que aparecen en la fila {(x,z) : x≠z \in Z}, y que C z sean los colores que aparecen en la columna {(z,y) : y≠z \in Z}. La condición de coloración es que cada C z y R z es disjunta. Dado que hay un número finito de posibilidades para cada conjunto, encontrar z y z' distintos donde R z \= R z' y C z \= C z' . ¿Qué color es (z,z')? Bueno, está en R z' (y no C z' ), y está en C z (pero no R z ). Así que es tanto en R z y no: una contradicción.
(Ninja'd. Drat. Bueno, prueba diferente al menos.)
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.
