12.8.05

968.- Problem(it)a

Tengo una recta: el plano se divide en dos partes.

Si tengo n rectas, no hay dos paralelas, ni tres que se corten en el mismo punto, ¿en cuántas partes se divide el plano?

18 comentarios:

Matias dijo...

\frac{n(n-1)}{2} + 1 ?

JuanPablo dijo...

si n=1, te da 0?
n=2 te da 2... n=3 te da 4, ajá, sí, hay un corrimiento de índices

Matias dijo...

Cierto!
\frac {n(n+1)}{2} + 1
Lo mas interesante, como siempre, es como se piensa.

Ivan dijo...

Respuesta tramposa: la secuencia A000124 de la Encyclopedia of Integer Sequences.

Dra. Lanfys dijo...

Argggh. Me hiciste pensar.
Me perdí con los anteriores eh...

A ver mi razonamiento:

- si tengo 1 recta sobre un plano, se me divide en 2 partes, como tu afirmación inicial. Pero si la recta no está SOBRE el plano, sino que "corta" al plano en un 1 punto, entonces no divido nada y entre recta y plano tengo 1 solo punto en comun.
Como afirmaste que cortaba, asumo que para el problema, las n rectas siempre estan SOBRE el plano.

- Si de a pares, ninguna es paralela (o sea siempre se cortan en alguna parte) y de a tres no se cortan en el mismo punto (pero de a 2 si, por lo que dije antes), entonces no queda otra que formar un triangulo entre las rectas.

Entonces:

Con n=2 (se cortan en 1 punto por no ser paralelas), me queda cortado en 4 areas.

con n=3 forma 7 areas: el triangulo y las 6 de alrededor... (o estoy equivocada?)

vean el dibujo 1 acá

- Con n=4, para cumplir lo mismo de antes, puedo:
una opcion es hacer un triangulo con alguno de los "vertices" donde se tocaban 2 rectas, se me cierra una de las areas y ahora tengo 10 triangulos.

vean el dibujo acá, es la parte en rojo

- Con n=5, otra recta mas, ahora tengo 15 areas

de nuevo otro dibujo, pero ahora en verde

Y yo pensaba que iba a llegar a alguna regla mágica... snif
1 > 2
2 > 4
3 > 7
4 > 10
5 > 15

:S

Y entonces????/

Dra. Lanfys dijo...

Ufff Ivan, y yo que me pasé 35 minutos dibujando y pensando y no hice refresh ... y vi tu post recien despues de escribir el mio... aaaaaaaghr! :*

Ivan dijo...

Quizás una forma de pensarlo es que como no hay dos paralelas, cada nueva recta corta a todas las demás (esto es intuitivo; es fácil convencerse). Cada nueva recta agrega tantas regiones como rectas precedentes, más una (esto no es tan intuitivo y habría que demostrar algo por ahí). Con 0 rectas en el plano hay 1 región; con 1 recta hay 1+1 regiones; con dos rectas hay 1+1+2 regiones, con tres rectas hay 1+1+2+3 regiones...

Matias dijo...

Algo parecido pense yo: tomas una recta que no sea paralela a ninguna de las anteriores, y la vas moviendo. Supongamos que se toman coordenadas y el eje x no es paralelo a ninguna de las rectas. Entonces uno toma las rectas y = c variando c. Eso da n puntos que "se mueven" sobre la recta. Cada vez que uno pasa por un cruce de dos rectas, lo que ve es que de los n puntos uno salta por encima de otro. Con cada salto hay una nueva region, y, como hay 1 + 2 + ... + (n-1) saltos, se tienen n(n-1)/2 regiones. A su vez, al comienzo se tienen n+1 regiones, porque uno empieza con n puntos. Se suma entonces n(n-1)/2 + n+1 = n(n+1)/2 + 1.
Caramba; es una de mis explicaciones mas confusas. Creo que me estoy superando :)

hernan dijo...

Yo lo pienso parecido a Ivan.

1. Si habia N-1 rectas y agrego la recta N, esta nueva recta corta a todas las anteriores. Son, por lo tanto, N-1 nuevas intersecciones.

2. Consideremos el segmento determinado por un par de intersecciones consecutivas. Es claro que este segmento parte en dos una region, o sea, crea una region nueva.

3. Ademas, la primera interseccion (igual que la ultima) divide en dos regiones (no acotadas) la region anterior.

4. Tengo entonces N nuevas regiones.
Llamo R(N) la cantidad de regiones determinadas por N rectas: la recursion entonces queda:

R(N) = R(N-1) + N

Con la condicion inicial: R(0)=1
(o R(1) =2, si prefieren)

5. Para solucionarlo, podemos ver que es la suma de una sucesion aritmetica (numeros consecutivos)
desplazada.
De ahi sale el resultado

R(N) = N (N+1) / 2 + 1

Igual, sospecho que deberia haber alguna forma deducir el resultado directamente, sin resolver la recursion.

manematico dijo...

hola jp. te mande como de costumbre una epistola digtalizada con mis ideas.

me sumo a la idea de que es 1 + \frac{n(n+1)}{2}

hernan dijo...

Por cierto, el que no quiera o no sepa resolver la ecuacion recursiva, que no quiera oir hablar de sucesiones artimeticas, y prefiera "verlo", puede hacerse este dibujito.

El numero en cada fila indica la recta agregada. Los asteriscos a la derecha del numero, las regiones que aporta esa recta.
La cantidad total de regiones, entonces, es igual a la cantidad total de puntos. Como se ve, es un triangulo (mas el asterisco de arriba).

0: o
1: o
2: o o
3: o o o
4: o o o o

La cantidad de puntos del triangulo sale facil, imaginando que es la mitad de un rectangulo.
Por ejemplo, para N=4

o + + + +
o o + + +
o o o + +
o o o o +

El triangulo de 4 x 4 es la mitad de un rectangulo de 4 x 5.
(4x5/2 = 10 puntos)
De ahi el N ( N + 1) / 2

hernan dijo...

Perdon, donde dice "asteriscos" deberia decir "circulitos"

De paso, el problema me recuerda este otro:

Sobre un plano, alguien marca un millón de puntos. En posiciones arbitrarias, el unico requisito es que son puntos separados.

Demostrar que siempre es posible encontrar una recta que no toca ningun punto y deja la mitad de los puntos de un lado y la mitad del otro.

JuanPablo dijo...

uf, ahora me da vergüenza meter mi respuesta...

DraL: muy honrado de que te tomaras la molestia de hacer los dibujitos!

Un truco que a veces funciona a partir de los casos particulares es mirar la diferencia entre dos consecutivos, de 2-4-7-10-15 se obtiene 2-3-4-5, y la respuesta ya casi se generaliza sola.

JuanPablo dijo...

Ivan - Hernan - Matías: ese es el estilo de solución que conocía, usando una recursión o inducción.

Como dice Ivan, está el paso "un poco turbio" de cuántas regiones se agregan. Yo en eso es donde soy de madera, "veo" que la cantidad de regiones que se agrega es del orden de n, pero me cuesta decidir sin pensar mucho si son n+1, o n-1.

JuanPablo dijo...

Manemático: usted es un Geómetra, no me caben dudas. Me tomo el atrevimiento de postear su solución.

Nop dijo...

Tal vez sea un poco tarde pero ahi va mi solucion:

Pienso el problema en C* o sea una esfera. Las rectas se transforman en circunferencias por el polo norte. Cada par de rectas determinan dos puntos, uno de los cuales es el polo norte.

Ahora pienso en vertices, aristas y caras (que son las regiones que hay que contar) y puedo aplicar la formula de Euler V - A + C = 2. Es facil contar A, con V hay que tener cuidado con los vertices repetidos. Luego despejamos C y obtenemos n(n+1)/2+1.

JuanPablo dijo...

nop, nunca es tarde, y menos para una solución de ese estilo!

Al final, voy a terminar posteando mi solución...

JuanPablo dijo...

Estimado Nop, te comunicarías conmigo por mail? (juandemairena, arroba, fibertel, com, ar)