Demostrar que $n$ líneas separan el plano en $\frac{n^2+n+2}{2}$ regiones

Question

Demuestra que $n$ líneas separan el plano en $\frac{n^2+n+2}{2}$ regiones si ninguna de estas dos líneas es paralela y ninguna de las tres pasa por un punto común.

Sé que empezamos con el caso base, donde, si llamamos a la ecuación anterior P(n), P(0), para las líneas 0 sería 0. Pero realmente no tengo ni idea de cómo empezar el paso inductivo. ¿Cómo sabemos a qué k+1 debemos llegar?

Gracias.

Answer 1

Esta es la forma en que suelo pensar en esto (en cierto modo utiliza la inducción).

Con $0$ líneas, hay $1$ región y ninguna intersección de líneas.

Cada vez que se añade una línea y ésta cruza $k$ otras líneas que añade $k+1$ regiones y $k$ intersecciones. Otra forma de ver esto es que para cada línea y $k$ intersecciones añadidas, $k+1$ regiones se añaden (el número de líneas e intersecciones añadidas).

Por lo tanto, el número de regiones es $1+\text{the number of lines}+\text{the number of intersections}$ . Con $n$ líneas, hay $\binom{n}{2}$ intersecciones (si no hay dos líneas paralelas ni tres coincidentes).

Así, el número de regiones es $\binom{n}{2}+n+1=\frac{n(n-1)}{2}+n+1=\frac{n^2+n+2}{2}$ .

Answer 2

Supongamos que dibujamos $n$ rectas en el plano de manera que cada par de líneas se cruzan (pero no $3$ las líneas se cruzan en un punto común). En cuántas regiones se encuentran estas $n$ ¿Las líneas dividen el plano?

Con $n = 1$ dividimos el plano en $2$ regiones. Con $n = 2$ tenemos $4$ regiones; con $n = 3$ obtenemos $7$ regiones. Una cuarta línea se reunirá con las otra $3$ líneas en $3$ puntos y así atravesar $4$ regiones, dividiéndolas en $2$ partes y añadiendo $4$ nuevas regiones. En general, el $n^{th}$ línea se añadir $n$ nuevas regiones:

$$u(1) = 2$$ $$u(2) = 4$$ $$u(3) = 7$$ $$u(4) = 11$$

Y así sucesivamente, donde $u(n) =$ número de regiones con $n$ líneas.

Obtenemos la relación de recurrencia:

$$u(n+1) = u(n) + (n+1)$$

Obtenemos la siguiente cadena de ecuaciones:

$$u(n) - u(n-1) = n$$ $$u(n-1) - u(n-2) = n-1$$ $$u(n-2) - u(n-3) = n-2$$ $$\vdots$$ $$u(4) - u(3) = 4$$ $$u(3) - u(2) = 3$$ $$u(2) - u(1) = 2$$

Sumando estas ecuaciones, obtenemos: $$u(n) - u(1) = 2 + 3 + 4 + ..... + (n-1) + n$$

Todos los demás términos de la izquierda se anulan entre filas, y nos queda:

$$u(n) = u(1) + 2 + 3 + 4 + \ldots + n$$

Lo sabemos, $u(1) = 2$

Así:

$$u(n) = 1 + (1+2+3+4+ \ldots+n)$$ $$\implies u(n) = 1 + \dfrac{n(n+1)}{2}$$ $$\implies u(n) = \dfrac{n^2 + n + 2}{2}$$

Así que:

$$u(n) = \dfrac{n^2 + n + 2}{2}$$

Nota: $\,$ Si se permiten líneas paralelas y más de $2$ para que las líneas se crucen en un punto, la relación anterior no se mantiene.

La respuesta depende entonces del número de líneas que se cruzan en un punto o del número de líneas que son paralelas entre sí.