miércoles, 30 de marzo de 2011

Una hormiga amenzada, una hormiga sin salvación

Como muchos ya sabréis, desde el diario El País, están publicando una serie de Desafíos Matemáticos con motivo del centenario de la Real Sociedad Matemática Española.

El pasado viernes, se publicó el segundo desafío a cargo del Profesor Fernando Blasco (autor del blog Mastemáticas, colaborador del Carnaval de Matemáticas), que llevaba por título Una Hormiga Amenazada (click en la imagen para abrir el video en una nueva ventana/pestaña):







El problema consistía en determinar si una hormiga que se mueve por las aristas de un cubo (como el de la imagen) y que parte del vértice formado por 2 aristas verdes y una amarilla, morirá o no a causa del insecticida que se ha aplicado a los vértices de la arista amarilla horizontal. Bueno, mejor que veáis el vídeo, que el amigo Fernando lo explica mejor.

Hoy mismo acaban de publicar también el vídeo con una solución muy simple (basada en simetrías, elementos básicos e intuitivos de probabilidad y la resolución de un sistema de ecuaciones) y que llega a la conclusión que La Hormiga no tiene salvación (click en la imagen para abrir el video en una nueva ventana/pestaña):








Si queréis saber lo que ocurre, la hormiga nunca podrá sobrevivir, morirá en el vértice 8 con probabilidad 4/7 y en el vértice 7 con probabilidad 3/7.

Yo llegué a la misma conclusión, pero por un método más complicado, utilizando matrices (al fin y al cabo es el mismo método, pero trabajando con todas la posibles ecuaciones, y no solo con las que Fernando utiliza). Como es complicado de escribir, lo envié en formato PDF y os lo dejo aquí para que lo veáis.




Lo que no sé, es si esta vez he ganado o no. Supongo que, como no he recibido notificación alguna, será que no... en fin, otra vez será. A esperar al tercero.

Tito Eliatron Dixit

12 comentarios:

  1. Veo que te has currado mucho la respuesta en PDF. Yo también supuse que la probabilidad de que la hormiga muriera era el 100%, aunque me dio pereza calcular las probabilidades de que muriera en uno u otro vértice, si bien parecia obvio que fuera cercana a 1/2 para cada vértice, algo superior para el vértice más cercano al punto de comienzo.
    Lo que es paradójico es que el modelo en sí está tan sesgado que aunque la probabilidad de muerte en él sea total, en la vida real, una hormiga tiene un desarrollado sentido del olfato que podría llevarle a evitar perpetuamente (durante toda su corta vida) los vértices con insecticida, sin más que dando vueltas a los varios bucles que pasan por los vértices no mortíferos. Es un caso de modelización desatinada de la realidad, en la que la probabilidad de supervivencia real, sería bastante superior a ese 0+. Estas paradojas ocurren en las empresas continuamente y se deben a un déficit de información en la toma de requisitos del problema que conduce a un modelo excesivamente simplificado. Claro que para un concurso, está más que bien. ¡A ver qué nos depara el tercero!

    ResponderEliminar
  2. Hola Eliatron!

    Yo envié una solución muy parecida a la tuya, puesto que también planteé la matriz que comentas. Yo lo he resuelto modelando el problema como una cadena de Markov. Bastaba con aplicar una formulita para obtener los resultados que han salido.

    Un saludo ;)

    ResponderEliminar
  3. Como te podrás imaginar por lo que te comenté en twitter, mi solución es como la tuya (la tuya no la he leído, simplemente la he ojeado y tiene pinta de ser exactamente igual).

    Una cosilla que se me ocurrió después era que si a la matriz que has presentado, en el puesto (7,7) y en el puesto (8,8) añadimos un 1, entonces los 2 últimos elementos de la primera fila de A^n nos daría la probabilidad acumulada el día n-ésimo y esto hace que en vez de hacer un sumatorio, nos toque hacer un límite de una expresión más sencilla. No obstante no he comprobado cómo saldría la matriz Jordan.

    En fin, voy a ver ahora la solución propuesta por el periódico, que todavía no la he visto.

    ResponderEliminar
  4. @Carlos: sí me imagin´çe que iba por el mismo camino.

    @Rafalillo: lo sé, esa era mi demostración técnica, pero es que me gusta más una explicación algo más mundana. Lo que yo he escrito es, al fin y al cabo, una demostración (para este caso particular) del teorema que tú ahs usado ($$(I-Q)^{-1}R$$ ¿no?) Para demostrar ese teorema, tras una reordenación de vértices, se llega a una matriz de similares características a la tabla que yo propongo... y ya es cuestión de argumentar de forma parecida a como lo hago para obtener el resultado general.

    Con el método que yo doy, se puede encontra la probabilidad de morir partiendo desdde cualqueir vértice, sin más que quedarte con la fila apropiada de $$A^n$$ ó $$(I-A)^{-1}R$$

    ResponderEliminar
  5. Exacto, ésa ha sido la expresión que yo he usado. Como bien dices, al calcular la matriz resultante de tamaño 6x2, tienes a los vértices 1-6 en las filas y a los vértices 7-8 en las columnas, y cada elemento te dice la probabilidad de morir partiendo de un vértice 1-6 a uno de 7-8.

    Yo intenté buscar una explicación más sencilla, pero no daba para más :D

    A ver si nos llevamos alguna vez el premio ;)

    ResponderEliminar
  6. Hasta donde yo sé, tampoco me he llevado yo el premio :D

    Esta vez me imagino que ha mandado menos gente la solución que la anterior.

    Por cierto, la solución oficial que dan, es más sencilla pero realmente es algo más complicada de lo que ahí se pone. Primero, una de las ecuaciones que saca, la saca de que la probabilidad de que la hormiga muera es 1, pero no demuestra que es 1, simplemente dice que debe de ser 1 porque se movería infinitamente. Y ciertamente eso parece, pero a veces al formalizar algo nos llevamos alguna sorpresa (como en el problema de la oruga y el árbol que tengo en mi blog). Por otro lado, el resto de ecuaciones tampoco son tan claras. Me explico:

    La probabilidad de ir de 1 a 8 dice que es 1/3 de la probabilidad de ir de 1 a 5 + 1/3 de la probabilidad de ir de 1 a 4. Pero... ¿qué significa exactamente la probabilidad de ir de 1 a 4? Pues bien, esa probabilidad sería la de en algún momento haber llegado allí. ¿Y la ecuación funciona? Pues ciertamente, pero para comprobarlo realmente habría que ver que esa probabilidad de 1 a 4 es un sumatorio y que cada sumando del sumatorio aportaría 1/3 de su valor a la probabilidad de 1 a 8. Al final sacando factor común el 1/3 la ecuación valdría.

    Vamos, que es correcto, pero que los pasos pueden quedar un poco oscuros, no sé si me entendéis.

    ResponderEliminar
  7. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  8. Yo no entiendo una cosa de este problema(aunque apenas sé de probabilidad).Y es el número de pasos que da la hormiga.
    Está claro que siempre hay varios caminos que no desembocan en la muerte, pues en el problema se dice que puede volver al mismo sitio...
    Entonces, supongamos que un camino posible es 1-2,2-4,4-3,3-1 y vuelta a empezar. Las probabilidades de que elija 1-2 son de 1/3, las probabilidades de que elija(a continuación) otro camino no mortal serían de 2/3, etc. Tenemos que la probabilidad total para n pasos sería de $$\frac{1}{3}·(n\frac{1}{3}·(n-1))^n$$ (si no me equivoco,lo que quiero decir es que la probabilidad de un camino de supervivencia desciende con cada paso adicional.Es como la probabilidad de que, si en una caja hay 10 bolas rojas y 10 blancas, las probabilidades de sacar las 10 rojas seguidas)
    De ahí que yo piense que el número de pasos sea fundamental.Porque además no existe un unico camino con posibilidad de sobrevivir.
    Está claro que, como la probabilidad desciende con los pasos,el número de éste importa. Imagino que la clave está en suponer infinitos pasos, pues la probabilidad de supervivencia tiende a cero.

    ResponderEliminar
  9. Esta es una solución que dieron antes de tiempo
    http://spltmatematicas.blogspot.com/2011/03/una-hormiga-amenazada.html

    Al estilo de la oficial, pero algo más simple (creo).

    ResponderEliminar
  10. ProfesorFrink: tienes mucha razón, el nº de pasos es muy importante. De hecho, en el problema se permiten un número infinito de pasos, de ahí que la probailidad de vivir sea 0.

    Si los restringimos... ya no sería 0.

    ResponderEliminar
  11. Vaya, acabo de ver ahora bien tu solución y aunque empezaba parecida a la mía, es distinta, es menos laboriosa en cuanto cálculo. Yo al final hacía la potencia n-ésima de A (bueno, en realidad solo la primera fila de la potencia) y con ello sacaba la probabilidad en 7 y 8 el día n-ésimo. Después sumaba las series (de números reales) que me salían que eran sencillas de sumar ya que cada serie era la suma de dos series geométricas.

    Bueno, en realidad no usaba la matriz A sino una de 8x8, pero vamos, las 2 últimas filas eran de 0's así que al final la diagonalización salía igual. Podría haber usado tu matriz A de 6x6. Visto lo visto me imagino que mi primer comentario del hilo no se entendía muy bien.

    P.d. Ya le vale al del spltmatematicas publicando la solución antes de tiempo...

    ResponderEliminar
  12. Yo lo resolví también como una cadena de Markov, como el límite de la potencia de la matriz de transiciones. Aunque luego utilicé una combinación lineal de los autovectores de los autovalores nulos de I-A para obtener el límite.

    Además, por pura diversión hice un programita de simulación, en plan Montecarlo. Maté unos cientos de millones de hormigas. Lo cierto es que la cosa converge muy lentamente hacia la solución, pero por supuesto que lo hace.

    ResponderEliminar

Si no comentas, Gauss se comerá una integral.
Y, por favor, respeta a todos con tus opiniones.