Número de regiones en el plano definido por $n$ líneas de Zig-Zag

Question

Los becarios de las Matemáticas.SÍ, he estado rascando mi cabeza en una solución a un ejercicio de Donald Knuth Concretas de las Matemáticas. Aquí está el problema:

Aquí está la solución (me escondí en caso de que alguien quiere resolver esto por su cuenta)

Dado $n$ líneas rectas que definen $L_n$ regiones, podemos sustituirlos por muy estrecho, en forma de zig-zag, con los segmentos de tiempo suficientemente largo que hay nueve intersecciones entre cada par de zig-zags. Esto demuestra que $ZZ_n = ZZ_{n−1} +9n−8$, para todos los $n > 0$; en consecuencia,$ZZ_n = 9S_n −8n+1 = \frac{9n^2 − 7n}{2} +1$.

$L_n$ es el número de regiones definibles por $n$ líneas, que se resuelve como un ejemplo anterior en el texto. Es igual a $S_n + 1$ donde $S_n = \sum_{k=1}^n k$. Yo estoy teniendo dificultad para la comprensión de la recurrencia de la solución. Voy a ocultar mi pregunta, sólo para ser más cuidadoso que yo no se echen a perder esta maravillosa problema para nadie.

¿De dónde viene el "$-8$"? Es la recurrencia entiende mejor como $ZZ_n = ZZ_{n−1} +9(n-1)+1$? O ¿que más contortos el significado de la recurrencia? Me imagino que no debe "-8" tiene que ver con "perdido regiones", debido a que la mitad de las líneas, pero estoy teniendo problemas para poner mi dedo en él.

Me encanta este problema, y me gustaría poder entender la solución en su totalidad! Gracias!

Answer 1

$ZZ_n = ZZ_{n-1} + n + 8(n-1)$.

Añadir una nueva línea recta primero, intersección de las líneas de $n-1$ anterior. Esto le da el término $n$. Luego realizar el pequeño ziz-zags como se sugiere en la pista. Esto agrega un % adicional $8$regiones en cada una de las intersecciones de $n-1$.

Answer 2

Tu observación es correcta. Si usted cree que el primer paso, hay intersecciones de $9(n-1)$ de la nueva zig-zag con la constelación existente. Ahora dos puntos de intersección consecutivos cualesquiera cortan una región acotada existente en dos regiones, resultando en un total de $9(n-1)-1$ regiones. Del mismo modo el segmento de línea entre el primer cruce e infinito y la línea segmento entre el último cruce e infinito cada corte una región sin límites existente en dos. Así que hay $9(n-1)-1+2$ nuevas regiones.

Answer 3

Lo que también funciona es cuando usted asume la primera asumir por cada línea zigzag que hay dos paralelas infinitas líneas y una línea infinita de intersección de ambos. Ahora, para el caso de la forma de zig zag líneas, cada línea paralela se detiene en la intersección con la tercera línea, así que usted tiene que restar 2 regiones de $L_{3n}$. La tercera línea está limitada en dos direcciones, por lo que usted tiene que restar dos regiones adicionales para cada línea zigzag. El último paso es restar 1 región debido a que las dos líneas paralelas no se cruzan. Por lo $$ZZ_n = L_{3n} - 5n = \frac{9n^2+3n}{2}-5n+1 = \frac{9n^2+3n}{2} - \frac{10n}{2} +1 = \frac{9n^2-7n}{2} + 1$$