Skip to content

Solución: recortando una elipse

by en 27/04/2014

¡Hola!

Se termina la semana y vuestro tiempo para darnos la solución al acertijo que os proponíamos el lunes pasado. En él, os preguntábamos cuál es el máximo número de regiones interiores que se pueden formar en una elipse si colocamos sobre su contorno un determinado número de puntos y pintamos líneas uniendo todos con todos. Como ejemplo, os decíamos que con 2 puntos se formaban 2 regiones, con 3 puntos se formaban 4, y con 4 puntos se formaban 8 regiones.

Concretamente, os preguntábamos cuántas regiones interiores se formaban poniendo 6 y 10 puntos diferentes. Si estáis habituados a los números binarios rápidamente os habréis percatado de que las soluciones de los ejemplos son las potencias de dos: 21, 22 y 23. La intuición podría en ese caso llevaros a pensar que con 6 puntos se formarían 25 regiones (32) y con 10 se formarían 29 (512). Pero… ¡os equivocaríais! De hecho, este acertijo (que se conoce como “el problema del círculo de Moser”) se suele utilizar como una prueba de que sacar conclusiones precipitadas utilizando sólo unos cuántos valores iniciales de una secuencia puede llevar a respuestas incorrectas 🙂

Pero nuestro lector Gualterio, que se está convirtiendo en un asiduo 🙂 no cayó en la trampa. Su respuesta, una vez más, ¡fue la correcta! Efectivamente, con 6 puntos se forman 31 regiones internas, y con 10 se forman 256. Como os decíamos el lunes, llegar a estas soluciones es cuestión de calma y tenacidad (especialmente la de 10 puntos). Pero la pregunta que Gualterio se contestó a sí mismo de una elipse con 100 millones de puntos y un total de 4.166.666.416.666.676.249.999.925.000.001 regiones está fuera del alcance del tiempo de una vida humana, de modo que claramente hay una solución mejor 🙂

La que os contaremos aquí necesitará hacer bastantes cuentas (repetitivas), por lo que, como os contábamos el lunes, es mejor resolverlo con un ordenador. Hay también una solución que puede utilizarse para calcular el resultado de una manera mucho más rápida que podría usarse incluso con una calculadora en unos segundos, pero llegar a ella es más complicado, a si es que, por una vez, nos conformaremos con la solución para programadores 🙂

Vamos allá. Lo primero de lo que hay que darse cuenta es de que cuando pintamos una nueva arista uniendo dos puntos, partimos en dos aquellas regiones por las que pasamos. Por ejemplo, si tenemos dos puntos, la figura que formaremos será similar a la siguiente:

Elipse con dos puntos

Si pensáis que al principio había una única región (ocupando el interior completo de la elipse), al dibujar la linea la región queda dividida en dos partes (no necesariamente iguales, claro). Dicho de otro otro modo, de una región inicial, hemos sacado dos, y por tanto el número de regiones totales se ha incrementado en uno.

Con tres puntos, la situación es similar a la siguiente:

Elipse con tres puntos

Al añadir el tercer punto, hay que pintar dos aristas nuevas, cada una de las cuales divide en dos la única región que atraviesa. Por tanto, cada una incrementa en uno el número de regiones totales, y pasamos de 2 a 4 regiones.

Con cuatro puntos el asunto se pone más emocionante:

Elipse con cuatro puntos

Fijaos en la linea que va del punto superior izquierdo al inferior derecho. Esa linea atraviesa dos regiones pues cruza una arista previa ya existente. Por tanto, significa que divide dos regiones anteriores pasando a formar cuatro más pequeñas. Por tanto, la arista incrementa en dos el número de regiones finales.

La conclusión que hay que sacar de este análisis es que cada nueva linea añade tantas regiones como lineas anteriores atraviese más una. Si lo pensáis un poco no os resultará difícil convenceros.

Por tanto, lo que necesitamos saber es ¿cuál es el número máximo de lineas que cruzarán las lineas nuevas? Para eso, vamos a añadir un quinto punto a la figura anterior, y pintaremos una única diagonal:

Elipse con cinco puntos y solo una arista desde el quinto al tercero

El nuevo punto es el etiquetado como 5, y hemos puesto una única arista, que lo une con el punto 3. Como podéis ver, cruza dos aristas previas (en los puntos a y b). ¿Por qué se corta en dos? Se corta en dos porque la nueva arista deja a un lado un punto, y al otro dos. Como todos los vértices están unidos con todos los demás, eso significa que hay 1×2 (=2) aristas que pasan de un lado hacia el otro, y por tanto, 2 cruces. Eso significa que esa arista genera 3 nuevas regiones internas.

Si en lugar de dibujar la arista uniendo el punto 5 con el 3 hubiéramos pintado la arista uniendo el 5 con el 4, en un lado no habría quedado ningún vértice, y al otro lado habrían quedado 3; 0×3 es 0, por lo que no hay corte de aristas y por tanto la arista 5-4 sólo crea una región nueva, al igual que, podéis comprobarlo, ocurre con la arista 5-1. Por su parte, la arista 5-2 cruza otras dos (como la 5-3), por lo que crea tres regiones más.

Una vez que nos hemos dado cuenta de esto, no es demasiado difícil generalizar. Por ejemplo, si tuviéramos ya colocados 7 puntos y estuviéramos colocando el octavo, tendríamos:

  • Dos diagonales que dejan 0 vértices a un lado y 6 a otro, por lo que ninguna se corta con nada y generan una única región (cada una).
  • Dos diagonales que dejan 1 vértice a un lado y 5 a otro, por lo que se cortan con 1×5 diagonales, y añaden 6 regiones cada una.
  • Dos diagonales que dejan 2 vértices a un lado y 4 a otro, por lo que se cortan con 2×4 diagonales y añaden 8 regiones cada una.
  • Una diagonal que deja 3 vértices a un lado y otros tres a otro, lo que genera 3×3 + 1 regiones nuevas.

¿Veis el patrón? Los que programéis, seguro que seréis capaces de hacer un bucle para realizar este cálculo. Además, esto hay que repetirlo para cada punto nuevo añadido (desde 1 hasta 6 o hasta 10 en nuestras dos preguntas), de modo que se necesitan dos bucles anidados. Si lo hacéis con un poco de cuidado, llegaréis a la solución dada por Gualterio 🙂

Aquellos lectores inclinados hacia las matemáticas (que alguno hay 🙂 ) en lugar de (o, quizá, “además de”) bucles también verán sumatorios. En ese caso, no es demasiado difícil (aunque sí un poco laborioso) escribir y desarrollar los sumatorios para llegar a un polinomio con el que calcular el resultado directamente, sin necesidad de un ordenador que nos ahorre el trabajo tedioso de iterar.

Y… para los matemáticos de verdad… este problema puede resolverse en realidad aprovechándose del invariante topológico de Euler (χ) que relaciona el número de aristas, vértices y caras de poliedros. Para eso, hay que considerar a la figura que estamos construyendo como un grafo planar por lo que su invariante topológico es 2. Usando combinatoria, se puede sacar el número de aristas y de vértices (interiores) que se forman a partir de los n vértices exteriores, y usar la χ de Euler para averiguar el número de caras (regiones interiores).

Pero… a los humanos normales nos sirve la solución de bucles 🙂 Si la programáis, recordad que podéis probar vuestra solución aquí (aunque necesitaréis utilizar enteros de precisión arbitraria).

¡Hasta el próximo!

Anuncios

From → Soluciones

One Comment
  1. Gualterio permalink

    Hola!

    Os cuento cómo lo resolví yo 🙂 Me quedé en la parte de los sumatorios, sin llegar a plantearme el tema del grafo planar 🙂

    Precisamente, lo que hice fue poner la fórmula en forma de sumatorios y empezar a desarrollar. Decis que el desarrollo es laborioso…. ¡¿laborioso?! ¿Eso es laborioso? ¡¡Es laborioso por mil!! Después de llenar unas cuantas hojas, decidí que había llegado el momento de parar 🙂 Así que abrí el maxima, uno de los programas matemáticos que hay en Linux, y dejé que hiciera los cálculos por mí 😀 Y llegué (llegó) a la solución polinómica que utilicé para llegar al número con 100 millones de puntos.

    Saludos!

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: