Colorear un tablero de ajedrez con una curva arbitraria

Question

Coge un papel y un bolígrafo. Coloca el bolígrafo en un punto de partida y empieza a dibujar una curva arbitraria sin retirar la mano hasta que hayas llegado al punto de partida. Puedes encontrarte con tu curva durante el dibujo en algún un punto intersecciones pero no más (como una intersección de líneas). Por ejemplo, la curva de la izquierda está permitida, pero la de la derecha no.

Ahora tu papel está dividido en algunas áreas. Llamamos a dos áreas "vecinas" si sus frontera común tiene más de un punto. Una "coloración" para las áreas del papel es tal que dos áreas vecinas tienen colores diferentes. Recuerda la coloración del tablero de ajedrez.

Pregunta: ¿Es cierto que existe una $2$ -colorear (Blanco y Negro) las áreas de un papel cuando dibujamos en él una curva arbitraria como se ha descrito anteriormente? En caso afirmativo, ¿por qué?

Un ejemplo: Nota a la coloración en la siguiente forma. Puedes probar con formas más complicadas por tu cuenta. Parece que siempre se puede hacer por $2$ colores.

Answer 1

Probablemente. Podemos crear un gráfico $G$ del dibujo asignando a cada región a colorear un vértice. Entonces, si $u$ y $v$ son vértices de $G$ , $(u,v)$ es una arista si y sólo si las regiones representadas por $u$ y $v$ compartir un rostro.

Esto debería dar como resultado un grafo bipartito que siempre es bicolorable, lo que a su vez implica que tu imagen es bicolorable.

Lo único que tendrá que demostrar es que $G$ es bipartita. Pero eso no debería ser demasiado difícil.

Answer 2

Colorea un punto de negro si el número de bobinado de la curva alrededor del punto es impar.

Answer 3

Si la curva es lo suficientemente suave, y hay finitamente muchas auto-intersecciones, la respuesta es sí. Sin embargo, para esta respuesta me voy a limitar a una clase particular de curvas: aquellas en las que a lo sumo dos bits de curva se cruzan en cualquier cruce, por lo que puede tener algo que localmente se parece a $\times$ pero no algo que se parezca localmente a un asterisco (*).

¿Por qué los requisitos de suavidad y finura?

Si piensa, por ejemplo, en el gráfico de $x^2 \sin \frac{1}{x}$ entre $-1$ y $1$ junto con el segmento del $x$ -eje entre $-1$ y $1$ y conectar los dos extremos con segmentos verticales, se obtiene algo con infinitas regiones, y se hace difícil decir si es realmente como un tablero de ajedrez.

Para el caso que he mencionado, he aquí una "prueba": elija una dirección $v$ con las propiedades que

1. la tangente a su curva está en dirección $v$ sólo finitamente a menudo, y

2. en estas tangencias, la curva se encuentra a un lado de $v$ o el otro (es decir, no hay "inflexiones" en los puntos donde la tangente es $v$ ).

3. Además, en cada cruce, ninguno de los vectores tangentes debe ser $v$ .

4. Todas las líneas en dirección $v$ intersecan la curva en un número finito de puntos.

5. Por último, la semirrecta entre dos puntos de cruce cualesquiera o dos tangentes cualesquiera no debe ser paralela a $v$ .

Estoy usando la suavidad a lo grande aquí. [La existencia de $v$ está garantizado por el Teorema de Sard, que no es un teorema fácil en absoluto, y no voy a demostrarlo aquí].

Gira las cosas para que $v$ es el positivo $x$ dirección.

Desde cada punto de tu curva-complemento, dibuja una semirrecta en el positivo- $x$ dirección. Cuenta el número de intersecciones de este rayo con tu curva. Si es impar, colorea el cuadrado de negro; si no, de blanco. No cuentes las intersecciones "tangentes", ni los cruces. Eso da un esquema de coloración; la única pregunta que queda es "¿es como un tablero de damas?".

Un argumento de "línea de barrido" se encarga de esto: considere la coloración de dos puntos muy cercanos en una región. ¿Son iguales? Compare las intersecciones de sus curvas de rayos: si los puntos están lo suficientemente cerca, las intersecciones de las curvas de rayos están próximas entre sí, y ya está... excepto en dos casos:

1. Un rayo es tangente a la curva y el otro no. Entonces el número de intersecciones de la segunda semirrecta es dos veces mayor que el de la primera, o igual, ya que la segunda semirrecta interseca la curva cerca de la tangencia dos veces o no la interseca (por el requisito de que la curva esté completamente a un lado de su línea tangente, es decir, la condición 2). (Estoy utilizando la condición 5 para asegurar que el rayo es tangente a la curva en un solo punto para que este análisis tiene sentido)

2. Los dos rayos tienen un cruce entre ellos. En realidad, esto no causa ningún problema, ya que la intersección del rayo1 con las partes que se cruzan puede emparejarse con las intersecciones del rayo2 con las partes que se cruzan. (Los detalles para esta parte utilizan la propiedad 3 y la propiedad 5)

Evidentemente, una región conectada tiene un color localmente constante y, por tanto, un color constante.

Evidentemente, si dos regiones comparten una frontera (son "países vecinos"), sus recuentos de intersecciones diferirán en paridad: Un rayo apuntando a la derecha desde un punto cercano a la frontera entre el país de la izquierda y el país de la derecha pasará a través de esa frontera; para un punto justo al otro lado de esa frontera (tal punto existe por la condición 4), el rayo apuntando a la derecha carecerá de esa intersección.

En resumen: ni siquiera afirmarlo con claridad es tan fácil, y demostrarlo tampoco es trivial. Es algo más sencillo si estás dispuesto a decir que tu curva es un polígono (posiblemente auto-intersecante) con un número finito de vértices (es decir, un "dibujo de unir los puntos"); en ese caso, las condiciones que he escrito más arriba son fáciles de verificar.

Creo que hay una prueba de una sola línea usando la dualidad de Alexander y la homología/cohomología mod-2, pero no es muy esclarecedora, y hay una tonelada de maquinaria detrás.

Answer 4

Intentaré dar un método intuitivo para colorear que no requiera mucha base matemática. Creía haber entendido claramente por qué funciona este método de coloreado, pero ahora lo dudo. En cualquier caso, intentaré dar un método de coloreado para cualquier dibujo que utilice sólo 2 colores sin presentar pruebas de validez (ahora no las tengo). Cualquier prueba de validez, o contraejemplo de que esto no funcionaría es bienvenido.

Intentaré explicar el método de coloreado con figuras. Utilicemos los colores 1 y 2 en lugar del blanco y negro.

Primero damos color 2 al plano. Colocamos el bolígrafo en un punto $p$ en el avión. Sin pérdida de generalidad, podemos suponer que dibujará un cruce en el punto $p$ . Mantenemos el color 1 en el lado derecho del bolígrafo y el color 2 en el lado izquierdo. Cuando llegamos a un punto de cruce, volvemos a colorear las dos caras "recién nacidas" con según qué lado del bolígrafo aparezcan en el punto de cruce (véase la figura). En cada cruce, intercambiamos los colores de los lados izquierdo y derecho del bolígrafo. Así hasta llegar al punto de partida.