Archivo de la categoría: matemática

Topológico

Hoy quiero hablar sobre topología. Desde que escuché hablar de esta rama de las mates siempre me ha parecido la más atractiva de todas. Está claro que la compartimentación de la matemática es un poco irreal, al final todo está conectado con todo, pero las definiciones, procedimientos y conclusiones de la topología me parecen muy bonitas y abren un mundo de posibilidades.

Y sí, sé lo que estáis pensando, cuando digo o escribo “topológico”, pienso en algo así:

Un topo lógico. ¡CHISTACO!

Un topo lógico. ¡CHISTACO!

Voy a intentar hablar de algunos conceptos de la topología que seguro que luego nos son útiles en futuras entradas ;)

Hay que decir que la topología es una rama muy abstracta, tan abstracta que podemos tocarla con las manos, como vamos a ver.

Muy agradecido a @twalmar por haberme iluminado en algunas dudas que han surgido en la redacción de esta entrada. Es un lujo contar con colegas así.

Sigue leyendo

Hasta el fondo

483586464Hoy nos vamos a parar a pensar sobre una pregunta que estoy seguro que más de una vez te ha dejado sin sueño.

Si sumerjo en aguja una piedra pómez durante 30 segundos, ¿llegará el agua hasta el centro de la piedra?

La respuesta evidente es que si la piedra es lo suficientemente porosa el agua llegará a su centro y si no es lo suficientemente porosa el agua no llegará a su centro.

Esa, sin duda, es la respuesta evidente, la menos evidente es que este problema dio origen a un campo de estudio que conocemos como:

PERCOLACIÓN

Esta teoría es interesante por diversos motivos de entre los cuales lo que más me impresionan son los siguientes:

a)  Es el modelo más simple en el que se puede apreciar una transición de fase.

b)  Las teorías matemáticas involucradas van desde los procesos estocásticos (azarosos) hasta la teoría de grafos.

c)  Sus aplicaciones son muy diversas e importantes en muchos ámbitos de la actividad humana.

Y quizás lo más importante es que uno puede jugar con los modelos con las manos, con lápiz y papel, con piezas de lego, con dados y monedas. Esto es lo que hemos hecho mi amigo Ventura y yo para probar de qué va esto de la percolación. Prometemos aprender a hacerlo con un ordenador para la próxima ;).

manual

Espero que la entrada, que ha quedado un poco larga, le guste a mi amigo Luís F. Rull.  Hace ya algunos meses, tomando café, me habló de la percolación que era un tema que yo tenía olvidado. Y después de muchas lecturas y de sorprenderme y maravillarme con el tema, al que nunca le había dedicado tanto tiempo, me he decidido a publicar esta entrada. Muchas gracias, Luís.

Sigue leyendo

No puedes demostrar que esta entrada sea ni verdadera ni falsa. Lo dice Gödel

Curiosamente hoy ha saltado la noticia de que han demostrado la existencia de un ser superior usando el teorema de Gödel. Ahora vendría un enlace, pero vamos que para lo que hay que leer mejor lo buscáis vosotros mismos.

Es curioso porque en un comentario a la entrada:

Diseña tu teoría física — Crash Course

Ya ha salido el susodicho teorema para concluir que las mates y la física son incompletas y por lo tanto no podemos confiar en ellas.

Esa conclusión, partiendo del magnífico trabajo de Kurt Gödel, es tan acertada como atribuirle al Quijote la expresión:

Cosas veredes, Sancho.

Pues sí amigos, cosas veredes.

En esta entrada vamos a intentar dar unas pinceladas sobre el teorema de Gödel y sobre sus magnífica y populares malinterpretaciones.

Sigue leyendo

El caos del panadero

Volvemos con temas caóticos, es lo que toca en los tiempos que corren. En esta entrada voy a hablar de uno de los sistemas que más graia me hacen en esto del caos.  Es un sistema simple, con transformaciones matemáticas que son reversibles y que sin embargo generan una dinámica caótica en los puntos que definen el sistema.

El tema que nos ocupará en estas líneas es la conocida como transformación del panadero. Veremos como de una forma simple, y muy visual, llegamos a ver el caos en el más estricto sentido de la palabra. La intención no es profundizar en el tema sino presentarlo de la manera más simple posible y dar los enlaces a determinados aspectos que me llaman la atención. Es una transformación, que me parece a mí, poco conocida y que es muy interesante.

En este blog hemos dedicado dos entradas a cuestiones caóticas:

Bienvenidos al Caos

La pregunta es… ¿se irá el sistema solar al carajo?

Así que no está de más meter una más sobre el tema. Espero que os guste.

Sigue leyendo

Te vi(gilo)

Clara y Raquel dibujadas por Raquel Garcia Ulldemollins  (Clara es la pelirroja)

Clara y Raquel dibujadas por Raquel Garcia Ulldemollins
(Clara es la pelirroja)

Francamente, tenía muchas ganas de aparecer por aquí. Tengo que reconocer que nunca antes me había conquistado la Física, a pesar de que algunos físicos no me caen nada mal… Pero quiere la vida que mi hijo mayor, al que llamamos amorosamente el gafotas, haya conseguido que me interese por ella. Y es que según él:

“Las mates molan, pero la Física sirve para hacer muchas más cosas”

Ya saben lo que dicen: cría cuervos

Al principio creí que se le pasaría, fases de las criaturas, pero desde que el pasado verano me despertara de la siesta para pontificar:

“Los matemáticos siempre presumís de que descubristeis la música pero la música no es más que una vibración y las vibraciones, mamá, son cosa de nosotros, los físicos.”

supe que, de momento, no había vuelta atrás.

Así que cuando Enrique me invitó a escribir una entrada en su blog el día de su segundo aniversario no solo no pude negarme sino que acepté con alegría y entusiasmo. Solo faltaba elegir el tema de la entrada y, claro, eso era fácil: si me lo pide Enrique, voy a hablar de flechazos. Ajá, de esos flechazos.

Hace pocos días tuve el placer de descubrir a una artista española, de Albacete para más señas, en uno de los conciertos gratuitos que, con motivo del día del Orgullo Gay, se celebran en las plazas de Madrid. Fue en la Plaza del Rey. Ella era Rozalén. Y sí, fue un flechazo. Más aún, cuando sonó esta canción:

Me vinieron a la cabeza muchos flechazos, muchos momentos de “te vi y, desde el primer momento, supe que eras ‘pa’ mí”.

Como es este un portal  de divulgación científica, de los mejores actualmente en lengua castellana, me limitaré a contar un flechazo científico, dejando para otra ocasión y para mi blog personal, quién sabe, hablar de los de que tiran del ombligo con aleteos de maripositas a las que no nos da la gana cortarle las alas.

orourkeEl flechazo científico al que me refiero tuvo que ver con este libro y muy especialmente con el primer capítulo del mismo: Polygon triangulation.

Más concretamente, lo que me atrapó en las redes de la, para mí entonces desconocida a pesar de ser ya licenciada en Matemáticas (otro día hablamos de planes de estudio y tal), Geometría Computacional y, en muchos sentidos, modificó mi vida, fue el Problema de la Galería de Arte.

No es la primera vez que hablo de este problema, los que me conocen deben estar cansados de oírlo, pero es que me parece fascinante. Trataré de ser breve, para que no me cierren las puertas de este blog ;)

Imaginemos que tenemos un gato metido en una caja cerrada y queremos saber en todo momento si está vivo o muerto. Sí, sí. Nada de incertidumbres, que a mí las incertidumbres me dan un fatiguita mu rara…

Queremos al gato en todo momento vigilado.

Usaremos cámaras de vigilancia dentro de la caja, en las esquinas de esta. La pregunta es: ¿cuántas cámaras son suficientes para asegurar que el gato está vigilado, se ponga donde se ponga? Si estáis pensando en una caja como un prisma rectangular (lo que viene siendo una caja de zapatos), la respuesta es fácil, ¿no? Con una cámara es suficiente.

Podemos pensar no en la caja completa y el dibujo tridimensional, sino en la base de la caja. Si la caja es un prisma rectangular, la base será un rectángulo.

No es difícil deducir que para vigilar un rectángulo es necesaria y suficiente una única cámara en una de las esquinas, debido a la ausencia de paredes que pudieran impedir la grabación en alguna zona de la caja.

(Nota: Estamos suponiendo que la cámara ve 360º a la redonda y tiene alcance ilimitado)

tevi_1

También, a poco que nos fijemos y juguemos con un lápiz y un papel, llegaremos a la conclusión de que si la base de la caja es un triángulo, un polígono cualquiera de 4 vértices o uno de 5, siempre es suficiente (y necesaria, claro) una sola cámara.

tevi_2

Ya con 6 vértices encontraremos cajas que necesitan 2 cámaras. De hecho, si exploramos los distintos polígonos de 6 vértices posibles, llegaremos a la conclusión de que para cualquier polígono de 6 vértices son suficientes 2 cámaras para vigilarlo. Aunque, no siempre son necesarias 2, como se puede ver en el hexágono regular de la derecha en la siguiente figura.

tevi_3

Podríamos decidir seguir con este estudio añadiendo un vértice cada vez al polígono que da forma a la base de la caja, pero sería tedioso y aburrido…

Así que os propongo un reto: si os digo solamente el número de vértices que tiene la base de la caja, ¿me podéis decir cuántas cámaras son suficientes para vigilarla, sea como sea el polígono de la base? Es broma, ¿eh? No es un problema para resolver en un rato ni mucho menos, de hecho, ese es básicamente el planteamiento del Problema de la Galería de Arte, cambiando la caja por un museo. Fue planteado en 1973 por Victor Klee y la primera respuesta la dio Václav Chvátal en 1975:

si el polígono es simple (no se cortan las aristas entre sí) y tiene N vértices, siempre serán suficientes \frac{N}{3} cámaras para vigilarlo. En realidad, \lfloor \frac{N}{3}\rfloor , esto es, la parte entera por defecto de \bf{\frac{N}{3}}. Es decir, que si tenemos 22 vértices, N=22, \frac{N}{3} = 7,333333333 y en este caso, \lfloor \frac{N}{3}\rfloor=7, el número que obtenemos, pero sin decimales.

tevi_4

Pues nada, lo que probó Chvátal es que si me dibujas un polígono muy enrevesado, todo lo enrevesado que quieras, con 22 vértices, por ejemplo, siempre serán suficientes 7 cámaras para vigilarlo. Sí, vamos a verlo con  el siguiente polígono:

tevi_5

Sin desprestigiar a nuestro amigo Chvátal al que admiro, no voy a usar su demostración para convenceros de que en el polígono del dibujo de arriba son suficientes 7 cámaras para vigilar todo el polígono. No.  Voy a usar la demostración que, de este mismo hecho, dio Fisk en 1978. Una demostración bella y cautivadora por su elegancia y sencillez, como todo en la vida en general y en las Matemáticas, en particular. De hecho, la extrema belleza de esta prueba de Fisk le valió que Erdös la señalara como candidata a estar en el Libro de las Demostraciones que, según él, tenía algún dios con las demostraciones más bellas e iba repartiendo a algunas mentes privilegiadas. Nuestro amigo Paul Erdös era más ateo que yo, si se puede. Lo del libro era una metáfora.

Bueno, que me derivo, vamos a repetir los argumentos de la prueba de Fisk para ver que en polígono de 22 vértices que acabamos de dibujar (lo he dibujado yo, pero bueno) son suficientes 7, \lfloor 22/3\rfloor, cámaras para vigilarlo.

Lo primero que vamos a hacer es triangular el polígono. Para ello, lo que hacemos es añadir todas las diagonales posibles (en amarillo) que sean interiores al polígono, que unan 2 vértices no consecutivos del mismo, y que no crucen a una ya dibujada. Esto es muy apañao además si queréis tener a alguien un rato entretenido dibujando rayitas.

tevi_6

Ahora vamos a colorear los vértices del polígono de tal forma que si 2 vértices están unidos por un segmento (ya sea blanco, de la frontera del polígono; o amarillo, si es una diagonal interior) no pueden estar coloreados con el mismo color. No lo vamos a ver aquí, pero Fisk demuestra en su trabajo que un polígono simple triangulado siempre se puede colorear (siguiendo la regla anterior) usando solo 3 colores. Ea, pues cogemos 3 Alpinos, de nuestros 3 colores favoritos y coloreamos.

tevi_7

Ya lo tenemos. Que sí, que lo tenemos.

Para asegurarnos de vigilar todo el polígono, bastaría con asegurarnos de que vigilamos todos los triángulos de la triangulación del mismo, ¿no? Los triángulos recubren todo el polígono, si todos están vigilados, lo estará también él. En todos los triángulos hay un vértice rojo, uno azul y otro verde. Si ponemos una cámara en cada vértice rojo, por ejemplo, ya hemos terminado. Claro;  puesto que en todos los triángulos hay, necesariamente, un vértice rojo, si en cada uno de estos, de los vértices rojos, ponemos una cámara, todos los triángulos estarán vigilados y ¡chim pón!

Pero no las vamos a poner en los vértices rojos, no, porque son 8, y estoy segura de que uno de los colores aparece, como máximo, 7 veces…

¿Que cómo lo sé? Por el Principio del Palomar.

¿Que cuál es el Principio del Palomar? Que si tienes más palomas que palomares, en uno de los palomares tienes que guardar más de una paloma.

¿Que qué tienen que ver las palomas con la vigilancia de gatos bicromáticos? Si tengo que colorear 22 vértices con 3 colores, es como si tuviese que colocar 22 palomas en 3 palomares distintos. En uno de los palomares, como máximo, hay 7 palomas, \lfloor 22/3\rfloor.

¡Anda que no! No pueden tener los 3 palomares 8 palomas o más, que, hasta donde yo sé, eso son 24 palomas como poco.

Efectivamente, si nos fijamos en el dibujo con los vértices coloreados, el color verde aparece 7 veces y también el azul. En este caso, podemos elegir cualquiera de los 2 para ubicar las cámaras, pero, en general, usaremos el color menos popular en la coloración de vértices, el que menos aparezca. Y, de nuevo, por el Principio del Palomar, será menor que \lfloor 22/3\rfloor.

Maravilloso, ¿que no?

Esto es un ejemplo  de cómo Fisk demuestra que \lfloor \dfrac{N}{3}\rfloor cámaras son siempre suficientes para vigilar un polígono con N vértices. Aquí tenéis el trabajo completo de Fisk.

La pregunta ahora es: ¿son siempre necesarias \lfloor \dfrac{N}{3}\rfloor  cámaras? Evidentemente, no, basta con pensar en polígonos redonditos (convexos) como este, que solo necesitan una cámara para controlar al gato:

tevi_8

 

Entonces, igual podemos mejorar el valor de Fisk, el de \lfloor \dfrac{N}{3} \rfloor, porque, a lo mejor, ningún polígono necesita nunca \lfloor \dfrac{N}{3} \rfloor cámaras, ¿no?

Pues no. A veces, son necesarias \lfloor \dfrac{N}{3}\rfloor cámaras:

tevi_9

Este fue el problema por el que, como dije al principio, sentí un flechazo por la Geometría Computacional y me enredé con ella.

En realidad, es una de las versiones más simples de este tipo de problemas, hemos supuesto que, por ejemplo, las cámaras graban 360º a la redonda y tienen alcance ilimitado… Os podéis imaginar, entonces, toda la variante de problemas, ninguno de ellos fáciles de tratar computacionalmente, que se derivan de este si, por ejemplo, limitamos el ángulo de visión de la cámara (pueden ser focos y queremos no vigilar, sino iluminar); o si limitamos el alcance de la misma; si permitimos que las cámaras se muevan; si queremos que cada cámara esté vigilada por otra cámara por motivos de seguridad; si en lugar de cámaras son routers que sí atraviesan paredes pero con restricciones… hay todo un mundo de problemas derivados del Problema de la Galería de Arte y todos son, al menos para mí, preciosos. Si me dejan volver a este blog, podemos explorar alguno de ellos otro día ;)

Ahora toca despedirse.

Felicidades a todos los cuentistas de este blog. Espero que sigáis adelante mucho tiempo y creo que mi gafotas también lo espera. Hacéis algo grande, de verdad.

Muchas gracias por la invitación, Enrique. Ha sido para mí un verdadero honor aparecer por vuestra casa. Y aunque la canción de Rozalén,  además de la Galeria de Arte,  me recuerda a la primera vez que nos vimos y me dijiste aquel “Hola”, me despido con una de mi Zenet que me evoca a ti, porque con este blog me enseñas a entender el Universo, también. 

¡Feliz cumpleaños, Fis!

Mati y Fis dibujados por Raquel para Mati y sus mateaventuras

Mati y Fis dibujados por Raquel para Mati y sus mateaventuras