Campamento de invierno 2020 de la MO coreana, problema de la prueba 1 P8

Question

Me he topado con un problema de teoría de grafos difícil. Traducido a grandes rasgos, es algo así:

Hay $n$ líneas trazadas en un plano: no hay dos líneas paralelas entre sí, y no hay tres líneas que se encuentren en un mismo punto.

Esas líneas dividirían el plano en muchas "áreas". Supongamos que seleccionamos un punto de cada área. Además, si dos áreas comparten un lado común, conectamos los dos puntos pertenecientes a las respectivas áreas con una línea.

Se habrá realizado un gráfico compuesto por puntos y líneas. Encuentre todos los posibles $n$ tal que exista un circuito hamiltoniano para el gráfico dado.

Este problema parece difícil de resolver: Hoy he intentado resolverlo pero no he podido; la pregunta también está publicada aquí (en la página de El arte de resolver problemas) pero nadie lo ha resuelto, así que ahora lo pregunto aquí. Gracias.

Answer 1

El gráfico es bipartito y tiene $\binom{n+1}{2}+1$ regiones, por lo que el problema sólo puede resolverse cuando $\binom{n+1}{2}+1$ es par: cuando $n \equiv 1,2 \pmod 4$ . Esto sugiere naturalmente un paso de inducción que va desde $n$ a $n+4$ , añadiendo cuatro líneas.

Esta es nuestra hipótesis de inducción: un $n$ -línea de configuración en la que suponemos que hay un ciclo hamiltoniano. He dibujado todos los vértices correspondientes a las regiones externas, y asumo que la arista roja que he dibujado es una parte del ciclo hamiltoniano. (Esto se hace sin pérdida de generalidad: algunas regiones externas tienen que tener grado $2$ por lo que serán adyacentes a otras dos regiones externas en el ciclo).

Ahora, añadimos cuatro líneas más, como se muestra a continuación, y ampliamos el ciclo con los vértices y aristas de color naranja:

Esto nos da una $(n+4)$ -configuración de la línea con un ciclo hamiltoniano, como se desee. Puedes ver que aunque he dado un dibujo con $n=5$ Lo que estoy haciendo en la parte de la "cuadrícula" del diagrama en la parte inferior derecha se extiende a cualquier $n>1$ .

El caso base $n=2$ es fácil; $n=5$ se deja como ejercicio al lector, porque lo dibujé pero se me olvidó guardarlo. (Asegúrese de comenzar con una configuración de línea que, si $2$ -colorear el $16$ regiones, ha $8$ regiones de cada color).

(En realidad, una solución para $n=5$ casi se deduce de $n=1$ pero no del todo, porque $n=1$ es un caso límite y tampoco tiene un ciclo hamiltoniano).