Número de regiones

Hay nuevos comentarios sin leer

Autor: ^DiAmOnD^ | Publicado el 7 de febrero de 2012
Categorías: Juegos | Imprime este post

29 comentarios

AM | 7 de febrero de 2012 | 12:41

Vótalo 0
No sé si entiendo muy bien el enunciado.
¿Hay que dar una solución única en función de n?

Para un caso sencillo con n=4, si unimos cada dos puntos (dos rectas) de manera que no se intersecten tenemos 3 regiones, pero si unimos los puntos de manera que las dos rectas se intersecten, tendremos 4 regiones.

¿Hay que dar el resultado como un rango de posible número de regiones?
AM | 7 de febrero de 2012 | 12:43

Vótalo 0
o ¿hay que trazar todas las cuerdas posibles entre los puntos?
Hilario Aquino | 7 de febrero de 2012 | 12:59

Vótalo 0
Mientras n va creciendo el numero de regiones es n + 1. Cuando n es infinito, entonces el numero de regiones es 1, la cual es la circunferencia misma.
Trackback | 7 feb, 2012

Bitacoras.com
Julián | 7 de febrero de 2012 | 13:37

Vótalo 0
Sea $r_n$ el número de regiones generadas al usar $n$ puntos.
por otro lado, supongamos que ya existen $q$ puntos en la circunferencia, y por lo tanto se han generado $r_q$ regiones.
En el momento en que adicionemos otro punto en la circunferencia, se tendrán que crear $q$ cuerdas adicionales. La pregunta es: ¿al crear estas cuerdas adicionales, cuántas más regiones se crearon?
Tomemos el caso en el que adicionamos una cuerda:
- si ésta solo atraviesa una región (no cruza ninguna cuerda) creará una región más.
- si atraviesa 2 regiones (cruza por 1 cuerda) creará 2 regiones más.
- si atraviesa 3 regiones (cruza por 2 cuerdas) creará 3 regiones más, y así sucesivamente. (todo esto ya que por definición no pueden haber tres cuerdas concurrentes en un mismo punto)
Por lo tanto, al adicionar una cuerda, si ésta cruza por $c$ cuerdas creará $c+1$ regiones adicionales. Dicho de otra forma, por cada cuerda adicional $a$ se crean $(\Delta r)_a = c+1$ regiones, siendo $c$ el número de cuerdas por las que se cruzó.

Ahora bien,
para $n=0$ existe una sola región que es el círculo. $r_0 = 1$ ,
para $n=1$ sigue existiendo la misma región. $r_1 = 1$ ,
para $n=2$ se crea 1 cuerda que cruza por $c=0$ cuerdas:
$r_2 = r_1 + (\Delta r)_1 = 1 + (0+1) = 2$
para $n=3$ se adicionarán 2 cuerdas más, en donde ninguna cruza por cuerdas anteriores ( $c=0$ ):
$r_3 = r_2 + (\Delta r)_1 + (\Delta r)_2 = 2 + (0+1) + (0+1) = 4$
para $n=4$ se adicionan 3 cuerdas, donde una de ellas cruzará por una cuerda anterior:
$r_4 = r_3 + (\Delta r)_1 + (\Delta r)_2 + (\Delta r)_3 = 4 + 1 + 2 + 1 = 8$
para $n=5$ se adicionan 4 cuerdas, donde 2 de ellas no cruzan cuerdas y las otras 2 cruzan de a dos cuerdas:
$r_5 = r_3 + (\Delta r)_1 + (\Delta r)_2 + (\Delta r)_3 + (\Delta r)_3 = 8 + 1 + 3 + 3 +1 = 16$
…
y siguiendo el mismo proceso se tendría algo así:
$r_6 = r_5 + 1 + 4 + 5 + 4 + 1 = 31$
$r_7 = r_6 + 1 + 5 + 7 + 7 + 5 + 1 = 57$
$r_8 = r_7 + 1 + 6 + 9 + 10 + 9 + 6 + 1 = 99$
$r_9 = r_8 + 1 + 7 + 11 + 13 + 13 + 11 + 7 + 1 = 163$
$r_{10} = r_9 + 1 + 8 + 13 + 16 + 17 + 16 + 13 + 8 + 1 = 256$

con lo anterior logro ver alguna secuencia, pero no del todo clara.
pretextos | 7 de febrero de 2012 | 13:40

Vótalo 0
el número de regiones en que queda dividida la circunferencia es:

R=2^(n-1)

donde n es el número de puntos.
Antonio A. | 7 de febrero de 2012 | 14:19

Vótalo 0
Hola,

Me parece a mi que será 2^(n-2) + sumatorio de i=0 hasta (n-2) de (n-2 sobre i). Siento no dominar el Latex
Todo ésto basado en el dearrollo de Julián.

Un saludo
M | 7 de febrero de 2012 | 14:20

Vótalo 0
Julián, tus valores coinciden con los de la sucesión $r_n=1+{n\choose 4}+\dfrac{n(n-1)}{2}, \;n\geq 5$ .
Ignacio Larrosa Cañestro | 7 de febrero de 2012 | 15:45

Vótalo 0
r(n) = Comb(n, 4) + Comb(n, 2) + 1 = (n^4 – 6n^3 + 23n^2 – 18n + 24)/24
Hay varias formas de verlo. Quizás la más rápida sea pensar en que ocurre
cuando vamos retirando cada una de las cuerdas. Si en ella había k puntos de
intersección, que la dividian en k + 1 segmentos, desaparecen k + 1
regiones. Al quitar otra, desapareceran k’ + 1 regiones, donde k’ es el
número de puntos que había en esa cuerda, después de retirar las anteriores.
En definitiva, al retirar todas las cuerdas, han desaparecido tantas
regiones como puntos de intersección y cuerdas había, y aún nos queda una,
el círculo completo. Luego si el número de cuerdas es c(n) y el de puntos de
intersección es p(n), el número de regiones para n puntos es:
r(n) = p(n) + c(n) + 1
El número de cuerdads es fácil de calcular: cada par de puntos produce una
cuerda. Por tanto, son Comb(n, 2).
En cuanto al de los puntos de intersección, por cada cuatro puntos en la
circunferencia hay uno, pues los cuatro puntos forman un cuadrilátero
convexo, y los segmentos que los unen son sus cuatro lados y las dos
diagonales, que se cortan en un punto en su interior. Por tando p(n) =
Comb(n, 4).
El número de regiones es
r(n) = 1, 1, 2, 4, 8, 16, 31, 57, 99, 163, 256, …
empezando por n = 0 (0 puntos, una región, todo el círculo). Es curioso que
desde n = 1 hasta 5 se corresponde con 2^(n-1). La “ley débil de los números
pequeños” nos hace pensar que r(6) debe ser 32, y resulta que no, que falta
una … Para mayor abundamiento, resulta que r(10) = 2^8 …
Maki | 7 de febrero de 2012 | 16:00

Vótalo 0
I see Pascal
AM | 7 de febrero de 2012 | 16:34

Vótalo 0
Julián, si quieres hacerla recursiva, tus valores serían:

$\displaystyle r_n = r_{n-1} + n-1 + \sum\limits_{i=1}^{n-3} (i)(n-2-i)$
Julián | 7 de febrero de 2012 | 17:06

Vótalo 0
si yo lo quisiera hacer recursivo sería como:
$r_n = 2r_{n-1} - r_{n-2} + 1 + \displaystyle\sum_{i=1}^{n-3} i$

de todas formas, la solución que ha dado Ignacio es más acertada:
$r_n = {n \choose 4} + {n \choose 2} + 1$
Walton | 7 de febrero de 2012 | 19:23

Vótalo 0
En todo caso, esa fórmula serviría para puntos que no forman un polígono regular de lado par…¿cuál sería la fórmula en este caso?
Ignacio Larrosa Cañestro | 7 de febrero de 2012 | 19:50

Vótalo 0
Ese es un problema algo más difícil. Aquí se describe como contar el número de puntos de intersección de las diagonales y el número de regiones:

http://math.mit.edu/~poonen/papers/ngon.pdf

Resulta sorprendente que el máximo número de diagonales que se cortan en un punto, distinto del central, es

2, si n es impar
3, si n es par pero no divisible por 6
5, si n es divisible por 6 pero no por 30
7, si n es divisible por 30

con la excepción de n = 6, en que el máximo es 2, y de n = 12, en que el máximo es 4.
Tipstk | 8 de febrero de 2012 | 01:31

Vótalo 0
Este problema me lo plantearon en mi entrevista para acceder a Oxford. Me sonaba y lo hice cortando el triángulo de Pascal en dos partes, es decir, utilicé números combinatorios.
Antonio Martín López | 8 de febrero de 2012 | 08:27

Vótalo 0
Un afectuoso saludo a Ignacio Larrosa Cañestro. Veo que sigue tan en forma como siempre. Desde que perdí la versión del programa “AGENT” para gestionar Correo y News no tenía noticias de Ignacio. Ha sido un verdadero placer.

Saludos
—–
Antonio Martín
Ignacio Larrosa Cañestro | 8 de febrero de 2012 | 12:47

Vótalo 0
Pues encantado de volver a oir de ti. Yo sigo frecuentando los mismos sitios de siempre:

Lista “matracas”: http://www.elistas.net/lista/matracas

(lamentablemente con muy poca actividad últimamente)

Lista “Snark”: http://www.snarkianos.com/

Grupo de news es.ciencia.matematicas: http://groups.google.com/group/es.ciencia.matematicas/topics

(o directamente con un lector de correo/news)

Y algunos otros, como este blog …

Por cierto ^DiAmOnD^, por mi, puedes eliminar esta entrada cuando estimes oportuno.
gaussianos | 8 de febrero de 2012 | 21:07

Vótalo 0
La dejamos Ignacio, así la gente puede conocer sitios nuevos donde se habla de matemáticas, si es que no los conocía ya .
Leumas | 8 de febrero de 2012 | 22:50

Vótalo 0
Para el caso n=4 el número máximo de regiones es 6.de 5 en adelante es 2n+1 donde n es el número de puntos y además la figura que se forma dentro es una estrella de n puntas
Omar | 15 de febrero de 2012 | 09:17

Vótalo 0
Pues a mi sale: $\frac{(\frac{n(n-1)}{2})(\frac{n(n-1)}{2}+1)}{2}$ para ello veamos primero cuantas regiones se crean por el número de cuerdas:

cuerdas regiones
0 1
1 2
2 4
3 7
4 11

se puede observar que si agregamos una cuerda más el número total de regiones se obtiene sumando el número de cuerdas que hay más el número de regiones que existian antes de agregar otra cuerda, así, si hay j cuerdas habrá $\frac{j(j-1)}{2}+1$ . Por otro lado el número de cuerdas que se pueden formar por m puntos es $\frac{m(m-1)}{2}$ , y de ahí obtenemos: $\frac{(\frac{n(n-1)}{2})(\frac{n(n-1)}{2}+1)}{2}$
Ignacio Larrosa Cañestro | 15 de febrero de 2012 | 11:29

Vótalo 0
Pero Omar, el problema original no es en cuantas regiones producen n cuerdas, sina cuantas producen todas las cuerdas determinadas por n puntos. No hay entonces posibilidad de dos cuerdas; el número de cuerdas es n(n – 1)/2.

Y Leumas, no se de donde sacas esas cifras: para n = 4, un cuadrilátero inscrito con sus diagonales, se forman 8 nregiones, y para n = 5, 16, …
Leumas | 15 de febrero de 2012 | 19:18

Vótalo 0
Ignacio, con todo el respeto, creo que te estas saltando un punto importante de las restricciones expuestas en el problema. ^^
Ignacio Larrosa Cañestro | 15 de febrero de 2012 | 20:07

Vótalo 0
Leumas, ¿que punto importante? ¿No se trata de colocar n puntos en una circunferencia? ¿De trazar la cuerda que une cada dos puntos? De contar el número de regiones cuando no pasan tres cuerdas por el mismo punto?

Aqui pueden contarse el númeo de regiones para n = 2 hasta 7 puntos:

http://www.xente.mundo-r.com/ilarrosa/GeoGebra/Regiones_circulo.html
Leumas | 17 de febrero de 2012 | 01:02

Vótalo 0
En esa bonita representación con geogebra, hay 3 cuerdas concurrentes en un punto, ese es el detalle.
Ignacio Larrosa Cañestro | 17 de febrero de 2012 | 01:25

Vótalo 0
Leumas, En la posición inicial del applet no veo ninguna, para ningún n de 2 a 7. De todas formas no hay problema, si te coinciden tres cuerdas en un punto interior, desplaza ligeramente uno de los extremos de cualquiera de ellas.
Leumas | 19 de febrero de 2012 | 21:28

Vótalo 0
¿Se va a decir la respuesta correcta de este acertijo?
M | 20 de febrero de 2012 | 00:24

Vótalo 0
Como se ha dicho anteriormente, el número de regiones es $r_n=1+{n\choose 2}+{n\choose 4}, \;n\geq 4.$ Veamos otra demostración, usando la fórmula de Euler para grafos planos:

- Tomemos $n$ puntos en la circunferencia y suprimimos los $n$ arcos formados. Entonces se obtiene un grafo plano conexo y simple, cuyos vértices son estos $n$ puntos y las intersecciones de las cuerdas en el interior del círculo. Ahora bien, elegidos cuatro vértices en la circunferencia se pueden trazar de una única forma dos cuerdas con intersección en un vértice interior del grafo. Luego el número de vértices en el grafo es $V=n+{n\choose 4}$ .

- En cada uno de los $n$ vértices en la circunferencia inciden $n-1$ aristas, mientras que en cada vértice interior inciden 4 (en virtud de la hipótesis de no concurrencia de tres cuerdas). Dado que hemos contado las aristas por duplicado, tendremos un total de $A=\frac{1}{2}\left(n\cdot(n-1)+4\cdot {n\choose 4}\right)={n\choose 2}+2{n\choose 4}.$

- La fórmula de Euler nos dice que el número de caras en este grafo debe ser $C=2-V+A$ . Excluyendo la cara exterior del grafo, y añadiendo las $n$ regiones delimitadas por los $n$ arcos de circunferencia suprimidos al principio, tenemos, que el total del regiones es:

$r_n=(2-V+A)-1+n=1+{n\choose 2}+{n\choose 4}, \;n\geq 4.$
Ignacio Larrosa Cañestro | 20 de febrero de 2012 | 00:33

Vótalo 0
En realidad, con la convención habitual de que Comb(n, k) = 0 si k n (D. Knuth por ejemplo), la fórmula es válida para cualquier número de puntos n >= 0.
Ignacio Larrosa Cañestro | 20 de febrero de 2012 | 01:14

Vótalo 0
Bueno, la convención que quería señalar es $\binom{n}{k}=0$ si n es menor que 0 o n es mayor que k.

Entonces, el número de regiones es:

$r_n = \binom{n}{4} + \binom{n}{2} + 1$

para todo n >= 0

Nota: ¿Cómo diablos se ponen los símbolos de mayor y menor en latex para que aparezcan correctamente? Los símbolos del teclado no funcionan y \lt, \gt parece que tampoco.