Angel "Java" Lopez en Blog

1 de Abril, 2011


Publicado el 1 de Abril, 2011, 11:50

Hace unos días me enteré de este problema, vía una lista de correo de programación en lenguaje Logo (en http://groups.google.com/group/logoes). El problema fue publicado por el diario ElPais.com en su versión online:

Una hormiga amenazada

Pueden leer ahí el planteo y hasta un video explicando el problema. Yo quiero plantearlo acá, y más adelante, en otro post, tratar algunas formas de solucionarlo.

Sea el cubo y sus aristas, numeradas para distinguirlas:

En el vértice 1 tenemos una hormiga (como ven, mis habilidades de dibujo son limitadas ;-). La hormiga siempre avanza desde un vértice por una de las tres aristas que tenga disponibles. Así, su primer avance puede ser desde 1 hasta 2, o desde 1 hasta 3, o desde 1 hasta 4. Elige cualquiera de esas opciones, con igual probabilidad (1/3 para cada destino). Luego, prosigue. Si está en el vértice 4, puede pasar a 1, 6, o 7, de nuevo, cada camino con igual probabilidad.

Pero en los vértices 7 y 8, alguien deja puesto veneno para hormigas. Si la hormiga llega ahí, muere.

El problema es: si la hormiga parte de 1, ¿Qué probabilidad hay de que la hormiga no muera nunca? ¿Qué probabilidad hay de que muera en el vértice 7? ¿Y en el 8?

Les dejo pensando la respuesta. Les propongo también extender el problema: ¿qué pasa con otros poliedros? ¿Y otros grafos? ¿Vivirá la hormiga con más probabilidad si sólo un vértice tiene veneno? Varíen el grafo, y la cantidad de vértices con veneno. ¿Qué pasa?

Nos leemos!

Angel "Java" Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez