$n$ líneas no pueden dividir una región del plano en $x$ regiones, encontrar $x$ $n$

Question

Me di cuenta de que $3$ que las líneas no se dividen el plano en $5$ regiones (se puede dividir en $2,3,4,6$ $7$ regiones). Tengo una línea de razonamiento para esto, pero me parece bastante ad-hoc. También me di cuenta de que no hay "lagunas" en el número de divisiones que se pueden hacer con $n=4$, yo.e podemos dividir un avión en $\{2,3,\cdots,11\}$ $4$ líneas.

Existe de todos modos para saber que si hay $n$ líneas $x$ el número posible de divisiones $\{ 2,\ldots, x,\ldots x_{max} \}$ donde $x_{max}$ es el número máximo de divisiones del plano con $n$ líneas, entonces ¿cuáles son los $x \lt x_{max}$ que no son posibles?

Para el correo.g, $n=3$, $x_{max}=7$, $x=5$ no es posible.

Answer 1

Vea si usted puede encontrar el papel, I N Schnurnikov, En cuántas regiones de $n$ líneas dividen el plano si en la mayoría de las $n-k$ de ellos son recurrentes? El resumen dice, entre otras cosas,

Por lo tanto, una nueva prueba de N. Martinov del teorema se obtiene. Este teorema determina todos los pares de enteros $(n, f)$ de manera tal que hay un arreglo de $n$ líneas que dividen el plano proyectivo en $f$ regiones.

O, si usted lee búlgaro, buscar Nikola Martinov, la Solución de un Federov-Grünbaum problema, Anuario Univ. Sofía Fac. De matemáticas. Informar. 87 (1993), no. 1-2, 73-85 (1999), MR1745340 (2000k:52020).

Espere un minuto - también en inglés: Nicola Martinov, la Clasificación de los acuerdos por el número de sus células, Discreto Comput. Geom. 9 (1993), no. 1, 39-46, MR1184692 (93 g:52008).

EDICIÓN 17 de Mayo: Véase también Oleg Una Ivanov, En el número de regiones en que $n$ líneas rectas dividen al plano, Amer Matemáticas Mensual 117 (Dec. 2010) 881-888. Curiosamente, este documento no hace referencia a Martinov del trabajo.

Answer 2

No tengo acceso a cualquiera de los documentos que, por desgracia, pero creo que he encontrado un handwavy prueba de dibujo que muestra que no hay lagunas distinta de $n = 3, x = 5$. La crítica es bienvenida; no estoy seguro de cómo hacer de este un argumento riguroso, y también tengo curiosidad por si hay un artículo que ya utiliza estas construcciones.

---

Supongamos $n - 1$ líneas que dividen el plano en 2 a $\frac{(n-1)n}{2} + 1$ regiones. Por lo suficientemente grande $n$, vamos a mostrar que el $n$ líneas que dividen el plano en $\frac{n(n-1)}{2} + 2$ a través de $\frac{n(n-1)}{2} + n + 1 = \frac{n(n+1)}{2} + 1$ regiones.

Considere la posibilidad de un arreglo de $n$ líneas que se divide el plano en $\frac{n(n+1)}{2} + 1$ regiones, de tal manera que, por simplicidad, las líneas están vinculados en grupos de dos, en la que cada línea en el $k$th par tiene una raíz en $k$ y la pendiente negativa de su pareja.

Si $n$ es impar, habrá una línea a la izquierda sobre el cual no puede ser emparejado; poner esta línea horizontal debajo de las raíces de los pares (por ejemplo,$y = -1$). Si $n$ es incluso, tomar la última pareja y poner una línea horizontal, como se describe, y la otra verticalmente en $x = 0$.

Podemos de la mano de onda a "tirar abajo" pares, uno por uno, por lo que su intersección descansa sobre la línea horizontal, restando una región para cada par "tirado". Esto termina la eliminación de $\frac{n-1}{2}$ regiones impares $n$, e $\frac{n}{2} - 1$ regiones para, incluso,$n$.

Luego podemos ir a través de cada par de líneas y ajustar la línea con pendiente negativa que tiene la misma pendiente que la próxima pareja de manera positiva con pendiente de la línea, el afeitado de una región cada vez (y la eliminación del mismo número de regiones como la operación anterior).

Para estas operaciones, nos llevará a $\frac{(n-1)n}{2} + 2$ por extraño $n$, e $\frac{(n-1)n}{2} + 3$ incluso $n$. Para llegar a $\frac{(n-1)n}{2} + 2$ incluso $n$, tomamos la última pareja de la línea positiva y ponerlo en paralelo a las primeras dos líneas verticales (restando dos regiones), y luego empujar el primer par ligeramente por encima de la línea horizontal (añadir).

Ahora tenemos que considerar cuando tales operaciones no se, para pares e impares de los casos. Ciertamente no podemos "tirar abajo" al $n \le 2$. Para $n = 3$, sólo tenemos un par por encima de la línea horizontal, por lo que no puede ajustar las pendientes como se ha sugerido, que nos da una brecha en $x = 5$. Para $n = 4$, sólo tenemos un par, y que no podemos compensar la brecha en$\frac{(n-1)n}{2} + 2$ -, pero, por suerte, no sólo podemos cubrir hasta las 8 de la región de la brecha de uso de 3 líneas paralelas y no paralelas de uno, sino de 4 líneas paralelas cubrir el 5-región de la brecha introdujo al $n = 3$.

Por lo que podemos utilizar estas técnicas para completar el proceso de inducción para $n \ge 5$.