$n$ líneas en un plano, adecuada coloración de puntos de intersección con solo 3 colores

Question

Dibujar $n$ líneas en un plano de tal manera que no hay líneas paralelas y no hay tres líneas de pasar por el mismo punto.

Cada punto de intersección es de color rojo, verde o azul. Demostrar que es posible el color de todos los puntos de intersección en un "buen" camino, de modo que cualquiera de los dos puntos adyacentes (como $A_i, A_j$) tienen diferentes colores.

Esto también significa que si usted "viajar" a lo largo de una línea arbitraria, va a cruzar $n-1$ puntos de intersección, constantemente cambiando de colores a partir de un punto de intersección a otra.

Mi primera (y última) tratar fue el uso de la inducción. Obviamente para dos o tres líneas, tenemos uno o tres puntos de intersección y con tres colores disponibles tenemos la base de la inducción demostrado. Sin embargo, la inducción de paso es más difícil. Yo era capaz de demostrar la inducción de paso si en cada posible combinación de líneas fue posible encontrar una línea que divide el plano en dos mitades con una media de no tener puntos de intersección. Sin embargo, que fue capaz de construir contra-ejemplos donde dicha línea no existe.

La última vez que traté de resolver un similar rojo-verde-azul problema descubrí la teoría de Ramsey. Me pregunto qué voy a descubrir este tiempo :)

Answer 1

Supongamos WLOG que las líneas son verticales-si no rotar el plano de hacer esto tan [asegúrese de que usted vea que esto es de hecho posible].

Permítanos color el conjunto de puntos de izquierda a derecha [no hay líneas son verticales, por tanto, para cada línea de $L$ , de hecho, hay una estricta orden de los puntos en $L$ de izquierda a derecha], con los colores de 1,2,o 3, como sigue.

1. El color es un punto más a la izquierda con el color 1. [Como sólo hay $<n^2$ puntos de hecho, hay un punto más a la izquierda. Elegir un punto arbitrariamente]

2. Deje $p$ ser un punto que satisface la siguiente: Dejar a $L_1$ e $L_2$ ser las dos líneas que contengan $p$ [, ya que sólo dos líneas se intersectan en un punto sólo hay dos $L_i$], todos los puntos a la izquierda de $p$ a $L_1$ [que recordar ni $L_1$ ni $L_2$ no es vertical] ya han sido de color y todos los puntos a la izquierda de $p$ a $L_2$ ya han sido coloreadas. A continuación, dejando $p_i$ ser el punto inmediatamente a la izquierda de $p$ a $L_i$; $i=1,2$; y la escritura como $c(p_i)$ el color asignado a $p_i$ para $i=1,2$ [$c(p_i) \in \{1,2,3\}$], deja que el color $c(p)$ de $p$ ser un entero en $\{1,2,3\}$ que no es ni $c(p_1)$ ni $c(p_2)$. [Hay, de hecho, siempre existe un $p$ mientras todavía hay incoloros puntos, un punto más a la izquierda de los puntos coloreados sin embargo, siempre es suficiente.]

Ver por ti mismo que el algoritmo anterior, de hecho, se termina, y que termina también con un adecuado 3-coloración.