31Ago/1136

El problema de Monty Hall

36 Comentarios    

Publicado por:Elio Campitelli.

Archivado en: Ciencia, Matemática

El problema de Monty Hall es una de esas eternas curiosidades que se rehúsan a desaparecer en el olvido. No sólo es muy anti-intuitivo y lo sigue siendo aún luego de comprender correctamente la solución, sino que inspira las emociones más profundas. Cuando fue postulado en la columna Ask Marilyn (donde los lectores de la revista Parade podían hacerle preguntas a la mujer con el Coeficiente Intelectual más alto del mundo) causó un revuelo entre sus admiradores e incluso matemáticos profesionales la criticaron por su respuesta (correcta). Voy a resumir el problema para los que no conocen. Los demás pueden hacer dibujos en sus cuadernos hasta que termine.

Resulta que estamos en un programa de televisión en el que el participante tiene 3 puertas para elegir. Detrás de una de ellas hay un auto, mientras que las otras esconden dos cabras. A menos que seamos amantes de las cabras, probablemente prefiramos ganarnos el auto. Luego de decidirnos por una de las puertas, el presentador (que para los estadounidenses se llama Monty Hall pero los argentinos podemos llamarlo Dady Brieva) para dar un toque de dramatismo abre una de las dos restantes que él sabe contiene una cabra y nos ofrece cambiar nuestra elección anterior. ¿Qué nos conviene hacer?

Si nos atenemos al sentido común, parece ser una pregunta con poco sentido. Las probabilidades de que el auto esté detrás de la puerta que hayamos elegido o de la otra no deberían cambiar por el sólo hecho de que Dady Monty Hall haya abierto una puerta. Si antes eran de 1/3, ahora también lo son. Otro razonamiento parecido podría hacernos pensar que, ya que ahora hay dos puertas, las probabilidades son 50% de que el auto se encuentre detrás de alguna de ellas. En cualquier caso, uno podría pensar que da lo mismo si cambio o no y decidir quedarse con su elección original. Por desgracia para el participante que piense de esa manera, va a volverse caminando con más frecuencia que quién decida cambiar.

¿Cómo podría cambiar las probabilidades previas el mero hecho de descubrir el contenido de otra puerta? Simple: el presentador no abre una puerta al azar, por lo que al abrir una puerta, Monty nos está dando información adicional.

Al principio del juego existe 1/3 de probabilidad de que hayamos elegido la puerta correcta. Esto significa que, tomadas en su conjunto, hay un 2/3 de que el premio esté en alguna de las dos otras puertas. Tanto la matemática como el sentido común nos dicen que si nos dieran a elegir entre quedarnos con nuestra puerta o elegir el conjunto de las otras dos, es preferible lo segundo.

A continuación Monty abre una de ellas y nos propone elegir entre la original y la que queda. ¡Efectivamente lo que nos está proponiendo es el caso descrito anteriormente! Sabemos que hay 2/3 de probabilidad de que el premio esté detrás de la puerta 2 ó 3. También sabemos que existe un 0% de probabilidad de que éste esté detrás de la puerta 3 (porque Monty sólo puede abrir una puerta con una cabra). Por lo tanto, el 2/3 ahora se "concentró" en la puerta 2. Nos conviene cambiar.

Si son como yo, aún luego de entender intelectualmente el problema les quedará una sensación visceral de incredulidad. No hay mucho que hacer: la probabilidad no es intuitiva. Una razón más para ser escépticos y desconfiar, principalmente, del juicio propio.

28Jul/1116

Mass Effect y los grafos.

16 Comentarios    

Publicado por:Elio Campitelli.

Archivado en: Ciencia, Mass Effect, Matemática

Aparte de estar interesado en la ciencia y el escepticismo me gustan los videojuegos. Aunque últimamente este hobby mío ha sido relegado a la participación en el Círculo Escéptico Argentino, me sigue gustando explorar nuevos mundos, conocer nuevos personajes, relacionarme con otras especies y vivir historias fantásticas. Y si bien hay toneladas de videojuegos que no van mucho más allá de disparar a todo lo que se mueve, hay otros – como el Mass Effect – que logran convencerme de que este medio es una forma de arte moderna con su propio lenguaje y potencialidad. El Mass Effect es uno de esos juegos en los que uno se mete en un universo complejo, rico, dinámico y verosímil (que tiene su propia wiki). Pero antes de que esto se convierta en el el blog del Círculo Gamer Argentino, vamos al punto.

Un Mass Relay en toda su gloria.

Como en casi todo universo de ciencia ficción acá hay viaje superlumínico (FTL para acortar). Sí, sabemos que esto no está permitido por las leyes de la física, pero lo dejamos pasar porque de otra manera sería imposible viajar por toda la Vía Láctea. La premisa que permite el FTL es que existe un “elemento cero” o eezo que al recibir una corriente eléctrica y “energía oscura“ produce un “campo de efecto de masa” (Mass Effect Field) que reduce o aumenta la masa del espacio-tiempo que lo contiene. Esto no sólo permite el FTL sino que también se usa para crear gravedad artificial. Toda una ganga. Pero si bien viajar a 1000 veces la velocidad de la luz es muy útil para cubrir ‘pequeñas distancias’ interestelares, si se quiere ir de una punta a la otra de la galaxia aún se tardarían 100 años. Para cubrir estas vastas distancias existe una compleja red de “Relés” (Mass Relays); máquinas gigantes en órbita que permiten cubrir grandes distancias de forma instantánea. Pero acá también hay una limitación y es que si bien con los Relés Primarios se pueden atravesar miles de años luz, éstos sólo se comunican con otro Relé Primario que es fijo. Los Relés Secundarios, por otro lado, se vinculan con cualquier Relé Secundario pero a distancias de sólo centenares de años luz.

Todo esto significa que la galaxia puede verse como un número de sistemas unidos por “corredores”. Este es un mapa de todos los sistemas estelares de los dos primeros juegos. Créditos a Daniel Weber, un usuario de Deviantart que parece que le gusta hacer mapas (recomiendo hacer click para agrandar y ver mejor los nombres de los sistemas estelares)

Esta red se supone construida por una antigua y gloriosa civilización ya extinta (otro cliché de la ciencia ficción) pero, suponiendo que estos sistemas son todos los que hay, yo veo un problema. Estos extraterrestres que eran tan inteligentes como para crear maquinarias colosales para cubrir distancias inimaginables de manera instantánea, al parecer, no cursaron Matemática I de Diseño Industrial. Me refiero a que no conocían la noción de Camino Hamiltoniano, uno de los conceptos más básicos de la teoría de Grafos.

Para empezar, un grafo es básicamente una serie de vértices unidos por aristas. Sé que no parece muy emocionante (y así me pareció la primera vez que me lo enseñaron) pero un matemático puede hacer carrera en donde una persona común no ve más que una serie de puntos unida por líneas. Los vértices tienen “grados”, que es la cantidad de aristas que inciden sobre ellos. En el mapa de arriba el Cúmulo Local (Local Cluster) donde se encuentra nuestro sistema solar, por ejemplo, está conectado a otros 4 sistemas; es decir, es de grado 4. Por otro lado la Nébula Omega es un vértice de grado 14.

Un grafo es completo si todo vértice está unido con los demás. La red de Relés no es un grafo completo, por supuesto, ya que se necesitarían [n × (n – 1)] ⁄2 pares de Relés Primarios. Para el caso tampoco es necesario que lo sea mientras se pueda llegar a cualquier sistema desde cualquier otro pasando por varios en el medio (camino). Es decir, mientras el grafo sea conexo. Tampoco es necesario que dos sistemas distintos estén unidos por más de un Relé; sólo hace falta que sea un grafo simple en contraposición a un grafo múltiple. Por una cuestión de seguridad, sería deseable que en caso de romperse un Relé el sistema no dejara de ser conexo. Para esto deberían existir al menos dos rutas para llegar a cualquier sistema estelar desde cualquier otro, pero mirando el mapa resulta claro que no es así; si, por ejemplo, el Relé de Hades Gamma tuviera un desperfecto, Gemini Sigma, Artemis Tau y el Voyager Cluster quedarían incomunicados del resto de la comunidad galáctica. Concluimos que este sistema no es doblemente conexo. Aunque como se dice que los Relés son prácticamente indestructibles tampoco parece ser una preocupación.

Los sistemas estelares del mapa también tienen varios colores que corresponden a su afiliación política; o sea que es un grafo coloreado. Sería conveniente para cada facción que se pueda viajar desde cualquier sistema a otro sin tener que pasar pos sistemas enemigos; es decir, que su componente sea conexa. Todas las facciones tienen esta ventaja salvo el Términus System ya que para llegar a Sentry Omega sí o sí hay que pasar por Attican Beta que es parte del Attican Traverse.

Grafo K 3,3 - Ejemplo de grafo no plano.

Hay una propiedad de los grafos que en este caso es irrelevante. Si mi grafo representara, por ejemplo, las uniones entre 3 casas y 3 servicios públicos (gas, electricidad y agua, por ejemplo) sería imposible representarlo de tal modo que ningún par de aristas se crucen. Ese grafo, conocido como el K3,3 no es un grafo plano. Como en este caso las conexiones entre los distintos sistemas estelares no son físicas, poco importa que se crucen. Distinto sería si se tratara de una red de rutas y trenes, por ejemplo, ya que un grafo no plano me obligaría a hacer pasos a nivel.

Finalmente, hay una razón por la cual desconfío de la sabiduría de los constructores de los Relés. Supongamos que una nave necesita transportar suministros a todos los sistemas de la galaxia, la red podría estar diseñada de tal forma que ésta pudiera visitarlos a todos sin pasar dos veces por el mismo sistema. Esto ahorraría tiempo y combustible (los motores FTL no son máquinas de movimiento perpetuo) pero es trivial mostrar que el grafo correspondiente a la red de Relés de la galaxia no tiene un camino Hamiltoniano. Aún mejor podría ser si tuviera un ciclo Hamiltoniano, es decir, que al terminar el camino Hamiltoniano uno vuelva al punto de partida.

Hay algunas formas de salir de este embrollo.Quizás la red de Relés antes era mucho más elaborada y grande pero durante los 50.000 años que sucedieron a la desaparición de sus supuestos constructores fueron cayendo uno a uno; quizás fue un trabajo inconcluso y el evento que desencadenó la extinción puso fin a tal faraónica empresa; tal vez el sistema de exploración impida el diseño deliberado. Finalmente, también es posible que los constructores fueran más vivos que nosotros y tuvieran sus propios motivos para diseñarlo de esta forma.

En cualquier caso, es interesante como con un poco de ojo es posible encontrar matemática y ciencia hasta en un videojuego.