Número de regiones

Vamos con el problema de esta semana. Ahí va:

Partimos de una circunferencia cualquiera y de n > 3 puntos de la misma. Para cada dos de estos puntos se traza una cuerda que los une de forma que no existan tres cuerdas concurrentes en un mismo punto dentro del círculo interior a la circunferencia. Determinar el número de regiones en las que queda dividido dicho círculo.

Que se os dé bien.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

28 Comentarios

  1. 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?

    Publica una respuesta
  2. 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.

    Publica una respuesta
  3. 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.

    Publica una respuesta
  4. el número de regiones en que queda dividida la circunferencia es:

    R=2^(n-1)

    donde n es el número de puntos.

    Publica una respuesta
  5. 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

    Publica una respuesta
  6. 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 …

    Publica una respuesta
  7. 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

    Publica una respuesta
  8. 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?

    Publica una respuesta
  9. 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.

    Publica una respuesta
  10. 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.

    Publica una respuesta
  11. 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

    Publica una respuesta
  12. 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.

    Publica una respuesta
  13. La dejamos Ignacio, así la gente puede conocer sitios nuevos donde se habla de matemáticas, si es que no los conocía ya :).

    Publica una respuesta
  14. 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

    Publica una respuesta
  15. 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}

    Publica una respuesta
  16. 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, …

    Publica una respuesta
  17. Ignacio, con todo el respeto, creo que te estas saltando un punto importante de las restricciones expuestas en el problema. ^^

    Publica una respuesta
  18. En esa bonita representación con geogebra, hay 3 cuerdas concurrentes en un punto, ese es el detalle.

    Publica una respuesta
  19. 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.

    Publica una respuesta
  20. 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.

    Publica una respuesta
  21. 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.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Vamos con el problema de esta semana. Ahí va: Partimos de una circunferencia cualquiera…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *