El Tamiz

Ignora lo accesorio, atesora lo esencial

Desafíos - Las habitaciones de la muerte (solución)

Me alegro de que hayáis disfrutado tanto pensando sobre el siniestro desafío de las habitaciones de la muerte: no sólo hemos recibido un montón de respuestas –casi un centenar–, sino que en muchas nos decís precisamente lo que os habéis divertido pensando sobre ello. Yo he disfrutado como un loco no sólo resolviéndolo por mi parte –de una manera mucho más burda que vuestras mejores soluciones– sino, sobre todo, leyendo las vuestras.

Casi la mitad de ellas llegan a la solución correcta, lo cual es estupendo pero, por otro lado, ha hecho muy difícil elegir finalistas y ganador. La elección será necesariamente injusta pero, si has llegado a la solución buena –sea como sea–, ¡enhorabuena! Incluso aunque tengas la solución correcta, te recomiendo que eches un vistazo a las otras soluciones y especialmente a los “extras” que habéis enviado algunos de vosotros.

Antes de nada, el meollo de la cuestión. La respuesta correcta es que la probabilidad de morir en A es de 1/6, la de morir en B es 1/3, la de morir en C es 1/6 y la de morir en D es 1/3. Pero ¿cómo llegar hasta aquí? Vuestras soluciones lo hacen básicamente de tres maneras distintas (con algún detalle diferente dentro de cada grupo, pero eso no es importante), de modo que analicemos cada tipo de solución.

El primer grupo de soluciones es el que podríamos llamar de fuerza bruta: usando algún lenguaje de programación, o una hoja de cálculo, o alguna cosa similar, básicamente se realiza el experimento un número muy grande de veces de modo que pueda verse qué sucedería con una especie de simulación.

Claro, hacerlo únicamente así no es la solución óptima –aunque es infinitamente mejor que no llegar a ninguna conclusión–, pero muchos de vosotros habéis usado este método, inteligentemente, para comprobar de manera pseudo-empírica la solución que habéis obtenido de una de las otras dos maneras. También es útil hacerlo así primero, para ver qué es lo que “debería salir”, y luego ponerse a hacerlo teóricamente con un rumbo determinado –eso es lo que hice yo, porque al principio no sabía por dónde empezar–.

De entre todas las soluciones de fuerza bruta, la mejor con mucha diferencia ha sido la de nuestro primer finalista, Sergio Cinos. Sergio ha utilizado javascript para realizar la simulación. Su solución me ha parecido fascinante por dos razones: por un lado, porque no da la solución simplemente de manera numérica, sino de forma gráfica, incluso del número de turnos que sobrevive cada desafortunado jugador.

Por otro lado, porque uno de los parámetros que se pueden modificar para ejecutar la simulación es el número de habitaciones. Como habéis dicho varios en la solución, este problema es atacable porque tiene una gran simetría, pero con cinco habitaciones, por ejemplo, hubiera sido bastante más difícil. Hablaremos de esto al final de la solución pero, armados con el programita de Sergio, podemos al menos saber qué debe salir para cada caso antes de enfrentarnos a él de manera teórica.

Sin más, os dejo disfrutar de la solución de Sergio, me lo he pasado bomba jugando con ella: http://eltamiz.com/images/2012/05/sergio.html.

Otra solución de fuerza bruta que merece mención es la de Javier Sedano (nuestro J de El Cedazo); Javier ha realizado la simulación en java, pero lo glorioso de su solución es la introducción, en la que explica la verdadera razón de la invasión de la Tierra, que no es otra que hacer trampa para resolver un problema matemático:

Lo que la historia no cuenta es que el general alienígena no tenía ninguna intención de invadir la Tierra. Fue a su jefe, mientras se estaba duchando por la mañana, a quien se le ocurrió este pequeño problema, y quien encargó a su subordinado que lo resolviera.

Nuestro general era un poco vago. No es que fuera mal matemático, claro que no. Eso es algo que los alienígenas matemáticos llevan en los genes. Es solo que él era vago.

Así que en vez de ponerse a pensar sobre el problema durante los escasos segundos que le hubiera llevado resolverlo, decidió poner a unos cuantos seres inferiores a jugar, a ver en qué habitación morían. El plan era simple: pondría a los 7 000 000 000 de humanos a jugar, mediría cuántos de ellos morían en cada habitación y con eso calcularía el porcentaje.

Con esto llegamos a la invasión de la Tierra, en la que nuestro alienígena esperaba encontrar casi siete mil millones de seres inteligentes con los que realizar el experimento. Con lo que no contaba el general es con las particularidades del ser humano:

La mayor parte de ellos simplemente dijo “A mí que me importa salvar al siguiente jugador. Paso. Que le den.” y directamente pasó de jugar. Esto falseaba el experimento, así que a quienes dijeron eso, hubo que descartarlos.

Otros, influenciados por un invento que ellos llamaban “televisión” se comportaron como si todo fuera mentira. Unos creyeron que estaban participando en algún tipo de reality show, por lo que se pusieron a insultar al alienígena y diciendo algo de que “estás nominado”. Otros dijeron noséqué de una película e intentaron agredir al alienígena. Obviamente, el alienígena tuvo que descartar a todos estos del experimento.

Otra parte sustancial de los humanos ni siquiera entendió el problema y optó por soluciones peregrinas, como correr en círculos ABCD o ADCB; ir a B o D y quedarse allí; quedarse quietos en A; o simplemente mirar al alienígena con cara de no haber entendido nada (estos, la mayoría). También estos hubo que descartarlos para no falsear el experimento. Una parte no despreciable si entendió el ejercicio, pero intentó hacer trampas, como por ejemplo quedarse quietos en A y decir que la probabilidad de morir en A era del 100%. Otra vez, hubo que descartar a estos, por tramposos, para no falsear la medida.

Solo un puñado de humanos, en torno a un millón, consiguieron hacer el experimento adecuadamente. El alienígena encontró una correlación aparentemente significativa entre esos humanos que sí lograron hacer el experimento y un panfleto pseudo-científico llamado El Tamiz (los humanos creen que es científico, pero es que son un poco retrasados, los pobres; todavía creen en el principio de incertidumbre y la contracción de la longitud… ilusos), lo que hace pensar al alienígena que quizá para las razas inferiores esa pseudo-ciencia es un paso necesario antes de llegar a la verdadera inteligencia.

El segundo tipo de soluciones es el que podríamos llamar iterativas. Son aquellas en las que se va calculando la probabilidad de muerte en cada habitación en cada turno, se van sumando esas probabilidades y se llega a una serie infinita. Dado que esa serie converge para cada habitación, se suma la serie infinita y se tiene la probabilidad de muerte en cada una de las cuatro habitaciones.

De entre ellas, me han parecido especialmente intuitivas las que dividen las probabilidades en dos tipos: puesto que empezamos en la habitación A, sólo es posible morir en las habitaciones B y D en un número de turno impar, y sólo es posible morir en A y C en un turno par. Pero mejor dejo que lo explique el segundo finalista de hoy, Argus:

Vamos a visualizar las probabilidades como si en lugar de una sola persona caminando por las habitaciones se tratara de un millón de individuos que en cada turno se dividen en dos grupos iguales y cada grupo va a una de las habitaciones contiguas.

Si empezamos con 1 millón en A, en el siguiente paso tendremos medio millón en B y medio millón en D. Con toda seguridad muere uno de estos grupos, bien en B, bien en D, y con la misma probabilidad.

Tanto si los supervivientes están en B como si están en D, en el siguiente turno una mitad va a A y otra mitad va a C. Uno de estos grupos muere, bien en A bien en D, de nuevo con la misma probabilidad.

Repitiendo este proceso vemos que por turnos, la mitad del ejército en el primer paso muere en B o D. La mitad de la mitad muere en A o C. La mitad de la mitad de la mitad muere en B o D y así sucesivamente.

Es decir, que la fracción de individuos muertos en total será:

$\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \frac{1}{32} + …$

Al final la suma es 1, es decir, mueren todos como era de esperar.

Pero como empezamos en la habitación A, los individuos que mueren en B o D corresponden a los turnos impares mientras que los que mueren en A o C corresponden a los turnos pares. O sea:

Probabilidad de morir en B o D = $\frac{1}{2} + \frac{1}{8} + \frac{1}{32} + …$. Probabilidad de morir en A o C = $\frac{1}{4} + \frac{1}{16} + \frac{1}{64} + …$

Resolviendo los sumatorios llegamos a:

P(morir en B o D) = 2/3

P(morir en A o C) = 1/3

Al movernos al azar, las probabilidades de B o de D son iguales entre sí y las probabilidades de A o de C también. Por tanto, la solución habitación por habitación se obtiene dividiendo estos resultados por 2:

P(A) = 1/6, P(B) = 2/6, P(C) = 1/6, P(D) = 2/6

De entre estas soluciones, además, ha salido una demostración adicional interesante, obtenida por Karlos y Alejandro Godoy: el tiempo medio de supervivencia en el juego. Dejo que lo explique Karlos:

Hay otra cosa que podemos calcular del problema (y es que si no se me hace muy soso). ¿Cuánto tiempo sobreviviremos de media?

Veamos, cada 5 segundos tenemos un 50% de probabilidades de morir. Es decir, tenemos un 50% de probabilidades de durar 5 segundos; un 25% de durar 10 segundos; un 12.5% de durar 15 segundos, y así sucesivamente.

Por tanto, el tiempo medio que tardaremos en morir vendrá dado por $\sum \frac{5n}{2^n}$, sumando n desde 1 hasta infinito. Esto podemos calcularlo como $\sum \frac{5n}{2^n}= 5 \sum \frac{n}{2^n}$ (sacando factor común), y la suma de la derecha da (de nuevo… calculadora o álgebra) exactamente 2.

Por lo tanto, de media sobreviviremos 10 segundos. No es mucho, pero siguen siendo muchos más de los que nos permitiría vivir nuestro alienígena si estuviera hambriento. Imagino que con el útlimo quedó satisfecho.

Finalmente, las que me parecen las soluciones más elegantes de todas, ya que no requieren de sumas infinitas ni programas que ejecuten la simulación, son las soluciones recursivas. Ojalá se me hubiera ocurrido una de éstas, porque me encantan y, al leerlas, se me ha encendido la bombilla, pero desgraciadamente mi mente no da para tanto. Enhorabuena a los “recursivos”, porque habéis convertido el problema en un juego de niños.

Básicamente, las soluciones recursivas se basan en darse cuenta de un hecho crucial: por un lado –como sucedía en las iterativas– que las habitaciones A y C, lo mismo que B y D, son equivalentes. Por otro, y aquí es donde está el detalle elegantísimo, que cada dos turnos el problema se convierte en el problema original de nuevo. Maravilloso.

Ha sido muy difícil elegir una solución entre las recursivas, porque son todas buenísimas; aunque no sea la ganadora, no puedo dejar de mencionar la de Mmonchi, porque fue la primera solución recursiva que recibí y, al leerla, se me pusieron los ojos como platos. El caso es que os dejo aquí la del ganador de hoy, Alberto Pérez, su “solución a las habitaciones de la muerte para ajedrecistas”:

El problema se simplifica mucho, si uno se da cuenta de las simetrías que presenta.

Es fácil darse cuenta que existe la misma probabilidad de morir en B que en D, Reflexionando un poco mas, la probabilidad de morir en A es la misma que la de morir en C.

Tenemos dos parejas, B-D y A-C

Para visualizarlo mejor, podemos pintar B-D de Blanco y A-C de Negro, eliminar los pasillo y quedarnos con un mini tablero de ajedrez de 2x2.

En este tablero nos movemos como torres, en vertical o en horizontal… pero no en diagonal. Por lo tanto, en cada movimiento se ira alternando de color, de la casilla en la que acabamos y en la que tenemos un 50% de probabilidades de encontrar la muerte: Blanco-Negro-Blanco-Negro-Blanco-….. hasta el trágico desenlace.

Esta secuencia podría ser infinita, sin tuviéramos tantísima suerte de ir salvándonos en todos los movimientos. Esta serie infinita, la podemos dividir en infinitos intervalos de 2 movimientos: Blanco-Negro.

En cada una de estos intervalos, el Blanco juega primero. Por lo que, la probabilidad de morir en una casilla blanca es siempre el doble que la de morir en una casilla negra.

Como tarde o temprano moriremos… La probabilidad de morir en una casilla blanca es de 2/3 y la de morir en negra es de 1/3. Pero para cada color existen dos casillas equi-probables. Por lo que hay que dividir a la mitad, quedando.

A= 1/6, B = 1/3, C = 1/6, D = 1/3

Una vez resuelto el desafío, os planteo una continuación: jugando con la solución de Sergio en javascript se puede ver, por ejemplo, que si hubiese cinco habitaciones las probabilidades de muerte se dividen en tres grupos: 15,8% en la habitación original, 31,6% en las dos adyacentes y 10,5% en las dos opuestas. ¿Alquien es capaz e obtener esa solución de manera teórica? ¿Alguien puede obtener conclusiones interesantes sobre la generalización a un número arbitrario de habitaciones? Si es así y me lo enviáis, volvemos a hablar del asunto de nuevo.

En cualquier caso, me alegro de que hayáis disfrutado pensando en el problema. Y lo más importante, como siempre, es que de ser invadida la Tierra por los Alienígenas matemáticos y vernos involucrados en un experimento como éste, estamos preparados.

¡Hasta el próximo desafío!

Desafíos, Matemáticas

43 comentarios

De: J
2012-05-13 13:06:01

Lo de los recursivos es impresionante. Una vez que lo lees, dices "¡Claro, es obvio, no puede ser de otra forma! ¿Cómo no se me ha ocurrido?".


De: Luis
2012-05-13 18:37:10

Hay una duda que me corroe. ¿No existe la probabilidad de que alguien se salve todas las veces?. Porque en cada iteración al menos siempre hay un 50% de probabilidades de no terminar aplastado. Aunque sea pequeña, eso quiere decir que el sumatorio nunca sería totalmente uno, ¿no?


De: Alejandro
2012-05-13 21:35:39

No luis, porque el experimento termina cuando mueras. Entonces el proceso en el mejor caso es infinito, por lo tanto no te puedes salvar "todas" las veces, porque son infinitas.
También hay que tener en cuenta que un humano no vive infinitos años, por lo tanto no puede sobrevivir al experimento.

Con respecto a las soluciones, están muy buenas. También me gustan las recursivas.


De: Luis
2012-05-13 22:12:53

No lo acabo de entender, Alejandro. Yo creo que probabilísticamente siempre existirá la opción de salvarse en un 50%. Es como lo de la moneda: aunque se hagan infinitas tiradas, existe la posibilidad de que, por ejemplo, salga siempre Cara. Y si morimos de viejos no sería por el experimento en sí sino porque nuestra naturaleza no nos permite vivir más tiempo...


De: Oldman
2012-05-13 23:30:15

La mejor literatura la de J ¡ya se nota que es un librepensador de El Cedazo! .

Pero para aceptar la solución en cifras como correctas (aunque no soy quién) le rogaría al gran jefe que, cantando bajo la ducha, nos fijó una "condición clave" y dijo "no vale, p.ej., moverte SIEMPRE entre A y B...." nos aclarase a algunos qué significado tiene esa alegre condición y si en los cálculos se ha tenido en cuenta de forma concienzuda.. .

A mí me da la impresión de que las soluciones expuestas incluyen las probabilidades de moverse ABABAB...(lo mismo para AD), incluso al azar, hasta morir después de 1º, 2º, 3º o enésimo tránsito, hasta el infinito, y que esta probabilidades habría que restarlas de las calculadas.


De: quake595
2012-05-14 00:04:42

la probabilidad de morir en A es de 1/6, la de morir en B es 1/3, la de morir en C es 1/6 y la de morir en D es 1/3.

Pues no lo entiendo, oiga. Una cosa es la probabilidad de morir en un momento concreto, y otra muy diferente es utilizar infinitas personas virtuales para contarlas y así averiguar donde muere que porcentaje de gente.

Siempre vas a tener el 50% de probabilidades de morir en el siguiente turno, y un 100% en infinitos turnos (o en el actual si decides no actuar).

De hecho, si quedarse en el sitio fuera una opción la probabilidad de morir sería del 66% siempre porque siempre habría 1 correcta de 3 posibles.

Entonces: 2/3 + 4/9 + 8/27 + 16/81 + [...] = 2

200% de muertos?? que coño??


De: hidrargyro
2012-05-14 06:41:23

Como les va gente, hace mucho que no comento algo :( Yo tambien habia llegado al mismo resultado, usando el metodo analitico que uso argus, solo que fue todo mentalmente y nunca hice tiempo de escribirlo, pero hace unos dias, me entro una duda con respecto al problema y lo lei de nuevo, para notar el detalle de que tranquilamente podia morir en alguno de los pasillos, asi que ya no estaba tan seguro de mi solucion. Igualmente espere hasta ver las respuestas de todos para saber si alguien lo habia tenido en cuenta y como lo habia afrontado, pero veo que Pedro no lo menciona nunca. Las respuestas actuales creo que apuntan a el caso de las cuatro habitaciones, todas pegadas como el mencionado tablero de 2x2 sin pasillos (y creo que esta bien haberlo pensado asi) pero me quede con ganas de ver alguna solucion que hiciera algun artificio con el tema pasillos :) Saludos!


De: Pedro
2012-05-14 07:12:28

Oldman, lo que dije (o quise decir, si no fui claro) fue que no vale, para "adivinar" cuál es la probabilidad, elegir un patrón fijo a propósito después de decir las probabilidades para asegurar que se cumplen, sino que hace falta suponer un movimiento aleatorio. Por ejemplo, no vale decir que hay un 100% de morir en A y luego quedarse allí. No vale decir que hay un 66% en B y un 33% en A y luego moverse de A y B todo el tiempo.

No es que valieran sólo algunos movimientos aleatorios, sino que estaba prohibido manipular los movimientos para que se adecuasen a una predicción trivial.


De: Pedro
2012-05-14 07:16:20

quake, no entiendo bien lo que te chirría pero, sobre todo, no entiendo lo del 200%. ¿Lo puedes detallar un poco más?


De: supernene
2012-05-14 09:29:24

mi respuesta es iguala la de Argus, solo hay una cosa que no entiendo:

Argus dice:

"Probabilidad de morir en B o D =1/2+1/8+1/32 . Probabilidad de morir en A o C = 1/4+1/16+1/64

Resolviendo los sumatorios llegamos a:

P(morir en B o D) = 2/3

P(morir en A o C) = 1/3"

..........yo llego a la misma conclusión observando que los mienbros de la primera suma son siempre el doble que los de la segunda, pero Argos parece que ha hecho las dos sumas infinitas.....¿puesdes indicarnos cómo?

resperto a la solucion de Alberto Perez, dice:
"En cada una de estos intervalos, el Blanco juega primero. Por lo que, la probabilidad de morir en una casilla blanca es siempre el doble que la de morir en una casilla negra."..........¿por qué?, a mí no me parece obvio......

saludos


De: Mmonchi
2012-05-14 10:39:58

Las probabilidades de morir en el caso de 5 habitaciones son 3/19, 6/19, 2/19, 2/19 y 6/19 para las habitaciones A, B, C, D y E. Pongo el método para calcularlo en limpio y lo subo.


De: alb.
2012-05-14 10:53:43

Si, si siiiiiiiiiii he ganado....
¡We are the champions my friends!
Campeón, campeoooón.
¡Yo soy español, español , español!
Me voy a una fuente para celebrarlo.

Lamentablemente y por culpa de las enfermizas introducciones de Pedro... no me atrevo a contar a familiares y amigos mi grandisima y épica hazaña.


De: Mmonchi
2012-05-14 11:32:49

¡Enhorabuena, Alb!

Para resolver el de las cinco habitaciones voy a resolver el caso de las cuatro habitaciones por un método más enrevesado que los ya explicados pero que tiene la ventaja de que es extrapolable a más habitaciones.

Empiezo definiendo un vector de probabilidades (w,x,y,z) que representa la probabilidad de morir en cada una de las cuatro habitaciones: w es la probabilidad de morir en A, x la de morir en B, y la de morir en C y z la de morir en D. El vector en la habitación A vale (a,b,c,d). Como hemos resuelto antes el problema, sabemos que realmente vale (1/6,1/3,1/6,1/3), pues a=c=1/6 y b=d=1/6. Pero esto es adelantar acontecimientos, de momento los valores de a, b, c y d son desconocidos.

Comienza el “juego” y me muevo a B o a D, con un 50% de probabilidades en cada caso. Una vez en la nueva habitación, puedo morir o salvarme con un 50% de probabilidades en cada una. Es decir, hay cuatro estados probables: que muera en B (MB), que me viva en B (VB), que muera en D (MD) o que viva en D (VD). Los cuatro tienen la misma probabilidad de ocurrir, 1/4.

Voy a calcular el vector de probabilidades de los cuatro estados. El de MB es fácil, si he muerto en B la probabilidad de que muera en B es 1 y las de que muera en A, C o D son 0: MB=(0,1,0,0). El de MD también es inmediato: MD=(0,0,0,1). Si estoy vivo en B tengo un vector de probabilidades con valores desconocidos VB=(a’,b’,c’,d’), pero en realidad estoy igual que al principio, en una habitación de la que me tengo que mover. La probabilidad de terminar muriendo en la habitación en la que estoy, b’, es la misma que tenía de acabar muriendo en la celda en la que estaba cuando estaba en A, es decir, a. Por tanto b’=a. Razono igual con la probabilidad de morir en la habitación de mi derecha (considero B a la derecha de A): es c’, y cuando estaba en A era b, luego c’=b. Análogamente llego a d’=c y a’=d, por lo que el vector VB=(a’,b’,c’,d’)=(d,a,b,c). Por el mismo método calculo el vector de probabilidades para el caso de que esté vivo en D, VD=(a”,b”,c”,d”)=(b,c,d,a).

Como las probabilidades del estado inicial son la suma de las de los cuatro estados a los que puede llegar, (a,b,c,d)=1/4(0,1,0,0)+1/4(d,a,b,c)+1/4(0,0,0,1)+1/4(b,c,d,a).

Ahora convierto los vectores en 4 ecuaciones con 4 incógnitas:

a=d/4+b/4, b=1/4+a/4+c/4, c=b/4+d/4, d=c/4+1/4+a/4.

Resolviendo llego a a=c=1/6, b=d=1/3, como ya sabíamos. No he tenido que deducir que b=d, ni que a=c, ni que a+b+c+d=1, cosas que eran evidentes pero que aquí obtengo por análisis.

Después de todo eso es fácil resolver el problema con cinco habitaciones. Los vectores son (a,b,c,d,e)=1/4(0,1,0,0,0)+1/4(e,a,b,c,d)+1/4(0,0,0,0,1)+1/4(b,c,d,e,a) y de ahí salen las cinco ecuaciones con cinco incógnitas que dan la solución. Los casos con 6, 7 o cualquier otro número de habitaciones se resuelven igual. En el de 6 se llega fácilmente a a=7/45, b=f=14/45, c=e=4/45 y d=2/45.


De: Alex
2012-05-14 15:34:46

Espectacular Mmonchi! Y enhorabuena a los ganadores!

Yo he obtenido una fórmula general, que da la solución para la habitación n de N habitaciones, aunque no es tan elegante como el método de Mmonchi (ni de lejos), no la pongo aquí porque no sería legible.


De: Karlo
2012-05-14 15:42:14

^^ ¡Me han publicado en el tamiz, me han publicado en el tamiz! Ahora mismo (o mejor, cuando tenga tiempo) me pongo a ver si saco el resultado para n habitaciones. De hecho, creo que ya sé como hacerlo para n=infinito... pero claro, ahí es más fácil porque no tenemos un círculo sino una línea recta; en todo caso, espero que de ahí salga un método para hacerlo.


De: Pedro
2012-05-14 15:42:31

Alb, ¿qué quieres decir exactamente con "enfermizas", guapín? ;)


De: alb.
2012-05-14 16:12:04

Digamos que cuando estoy leyendo la serie de los alienigenas matemáticos, y entra alguien en la habitación...pongo rápidamente pornografía para disimular y que no piensen que soy un pervertido.
;)


De: Argus
2012-05-14 16:51:26

Espectacular Mmonchi y además tan conciso y bien explicado. Eso de igualar el vector de probabilidades antes y después de moverse es una genialidad que no se me habría ocurrido nunca. Aún le estoy dando vueltas, no te creas. Lo inmediato es pensar que las probabilidades van variando con cada movimiento. Gracias por el regalo.

Pero si se permite a este pobre aficionado poner una objeción, diría que el método se complica mucho para un número mediano de habitaciones. Resolver por ejemplo 20 ecuaciones con 20 incógnitas es farragoso. Para 147 ya ni te cuento.

Es que algo me dice que tiene que haber alguna expresión general más sencilla, con ayuda de una tabla para sacar los coeficientes... no sé... al fin y al cabo las soluciones son quebrados sencillos en función del número de habitaciones y de su posición relativa respecto al punto de partida. Alex, a ver si te animas a esbozar cómo queda la expresión de la habitación n con N habitaciones :-D


De: Pedro
2012-05-14 17:00:39

Alex me ha enviado la solución genérica, pero tal vez quiera darle alguna vuelta más para hacerla más asequible. Cuando me lo digas la cuelgo para que la vean los demás :)


De: Igna
2012-05-14 17:05:16

Mmonchi, me acabas de dejar con el culo torcido. También con la solución al problema original de Alb me quedé estupefacto; muy elegantes ambas. Yo llegué a la solución por un método retorcido, extraño y dando más vueltas que una peonza, pero me lo pasé como un enano.
Por cierto, Pedro, tengo que decirte que: Desafío + Alienígenas Matemáticos = Épico.


De: Juan Carlos
2012-05-14 17:07:08

"Digamos que cuando estoy leyendo la serie de los alienigenas matemáticos, y entra alguien en la habitación…pongo rápidamente pornografía para disimular y que no piensen que soy un pervertido"
jajajajajajajaj :D :D

Yo pensé que la probabilidad siempre es 50%, es decir en una u otra habitación (muero en B, salvado en B, muero en C, salvado en C) o algo así ;)


De: Alex
2012-05-14 17:19:16

Por mi cuando quieras Pedro.


De: Pedro
2012-05-14 17:36:33

Hecho. Podéis echarle un ojo en http://eltamiz.com/images/2012/05/alex-n-hab.pdf


De: Alex
2012-05-14 17:47:43

Gracias! Ahora estoy intentando sumar el caso N->Infinito, ya que parece que al aumentar N los valores de la probabilidad se estabilizan. Aunque sumar series no es lo mio :_(.


De: txuripoket
2012-05-14 18:19:30

plas! plas! plas!! muy bueno mmonchi. un crack!

yo estaba sacando la solucion de 2 maneras mas arcaicas y sin nada de elegancia, pero una de ellas me ha dado alguna conclusion q puede ser erronea pero como en internet a lo maximo q puede llegar uno es a q le insulten, ahi van:

primero la mas tramposa, un atajo utilizando la logica (la clave es q sabemos la solucion):
las puertas adyacentes (b y e) a la primera puerta tienen la misma probabilidad y el doble de la 1º puerta(a), y las otras 2 (c y d), tienen 1/3 de probabilidad de las puertas b y e. sabemos q el sumatorio de todas las puertas es 1 o 100%. se iguala y despeja y ya esta.
para n soluciones, sabes q van emparejados, menos a y la ultima si es par. pero sigue la misma correlacion: b y la ultima el doble de a, luego tambien son el triple de los siguientes, luego el cuatriple,... y sabemos q el sumatorio de todas es uno. tachaaan. con eso pedro no te pone un 10 pero espero q un 5 si.

ahi va la segunda manera, es un poco "idea de bombero" pero he sacado alguna conclusion:
me he hecho un "arbol genealogico" o mas bien probabilistico. es dificil explicar sin exponerlo, pero mejor q lo haga cada uno q yo solo se hacerlo a papel y boli.

en ese arbol, arriba a, abajo e y b. de b sale a y c y de e: a y d.
se puede seguir hasta q te canses (despues de cada tirada, la siguiente rama tiene el doble que la anterior y la raiz cuadrada de la posibilidad anterior):
el tema es q en la primera rama (e y b) tienen una probabilidad de (1/2)^2, la siguiente rama, cada una tiene (1/2)^4, la siguiente (1/2)^6, luego (1/2)^8, etc... hay q tener en cuenta q de cada rama salen 2 (q son las puertas). y las ramas son las tiradas n caso de supervivencia.
asi se puede sacar tambien la probabilidad, luego sumando las probabilidades, haces un arbol de 5 tiradas, y con eso tienes mas del 90% de las probabilidades, sumas todas las probabilidades, y aplicas por la regla de 3, el % total q has hecho como si fuese el 100% de probabilidad, y tambien te sale.

entonces me he preguntado, porque 1/2? y porque en el problema original,por el metodo iterativo el primer sumando es 1/4? (25% de morir en b y d)
pues 1/2 es porque solo hay dos puertas cada vez, si pudiesemos elegir entre n puertas seria 1/n.
y el otro 1/2 es pq solo hay 2 estados, vivito y coleando o fiambre, si hubiese z estados, seria 1/z. entonces en la primera tirada, el % seria de 1/nz para b y d y luego dios dira...

se pueden sacar mas conclusiones viendo el arbol, pero no me voy a extender.

perdon por la txapa


De: txuripoket
2012-05-14 18:40:13

por cierto, si mmonchi ha utilizado vectores para calcular las probabilidades, imagino q para n puertas y z estados, se podrian utilizar matrices, no?


De: quake595
2012-05-14 20:59:53

Suponemos que la mitad de individuos mueren en el primer turno, la mitad de la mitad en el segundo, etc...
Si obtenemos la suma total: 1/2 + 1/4+1/8+1/16 + ... = 1
100% de muertos, nadie se escapa.
Pero si suponemos que 2/3 partes mueren (lo que sería dar a elegir 3 opciones, de las cuales solo 1 es la que te salva) y obtenemos la suma total:
2/3 + 4/9 + 8/27 + 16/81 + [...] = 2
200% de muertos, mueren el doble de los que hay??


De: Pedro
2012-05-14 21:54:13

quake, usas (2/3)^n, pero si mueren 2/3, sólo queda 1/3 vivos para morir el turno siguiente. La serie que obtienes, creo, está mal:

Turno 1: mueren 2/3

Turno 2: mueren 2/3 de los que quedan, es decir, 2/3 * 1/3 = 2/9

Turno 3: mueren 2/3 de los que quedan, es decir, 2/3 * 1/9 = 2/27

Turno 4: etc.

Y la serie, si no me equivoco, sigue sumando 1.


De: Mmonchi
2012-05-14 22:03:41

Argus, he pensado en lo que dices y llevas razón, se puede encontrar la solución mediante una serie de fracciones. Pero las fracciones se obtienen resolviendo el sistema de ecuaciones, que siempre tiene la misma forma: los valores de la matriz son 4 en la diagonal, -1 a derecha e izquierda de los 4 y en las esquinas opuestas, y el vector de los términos independientes vale (0,1,0,0,…,0,0,1). No voy a resolver aquí el sistema sino a dar la solución general, pero si alguien se anima verá que sale con relativa facilidad.

Hay dos soluciones, una para un número de habitaciones impar y otra para un número par. Voy a obtener primero la probabilidad de morir en cada habitación en el caso impar como fracciones de igual denominador. Para ello hago las siguientes operaciones: 3=6/2, 4-2/6=22/6, 4-6/22=82/22, 4-22/82=306/82, 4-82/306=1142/306, 4-306/1142=4262/1142,… En cada caso le resto a 4 el inverso del resultado anterior. Al quedarme con los denominadores obtengo la siguiente serie: 2, 6, 22, 82, 306, 1142,… que son los numeradores de la solución. Por ejemplo, si tengo nueve habitaciones tomo los cuatro primeros valores de la serie (la mitad entera) y los copio, primero al revés y luego al derecho: 82, 22, 6, 2, 2, 6, 22, 82. El valor que falta, el primero, es la mitad del mayor, de modo que la serie completa es 41, 82, 22, 6, 2, 2, 6, 22, 82. Como las probabilidades suman 1, el denominador es la suma de la serie, en este caso 265. Por tanto la probabilidad de morir en cada una de las nueve habitaciones es 41/265, 82/265, 22/265, 6/265, 2/265, 2/265, 6/265, 22/265, 82/265.

Ahora el caso con un número par de habitaciones. Es todo igual salvo que las operaciones empiezan con un 2 en lugar de un 3: 2=4/2, 4-2/4=14/4, 4-4/14=52/14, 4-14/52=194/52, 4-52/194=724/194, 4-194/724=2702/724,… La serie es 2, 4, 14, 52, 194, 724,… Por ejemplo, para diez habitaciones tomo los cinco primeros valores y los copio, primero al revés y luego al derecho, pero esta vez sin repetir el último: 194, 52, 14, 4, 2, 4, 14, 52, 194. El valor que falta para la primera habitación vuelve a ser la mitad del mayor, así que queda: 97, 194, 52, 14, 4, 2, 4, 14, 52, 194. Como suman 627, las probabilidades buscadas son 97/627, 194/627, 52/627, 14/627, 4/627, 2/627, 4/627, 14/627, 52/627, 194/627.

El término general de las dos series lo da la fórmula Xn = 4*Xn-1 – Xn-2 a partir de los dos primeros valores en cada caso. He puesto antes las fracciones que las generan porque es lo que se obtiene al ir resolviendo el sistema de ecuaciones, pero da lo mismo hacerlo de una manera o de otra.

Es curioso que al aumentar el número de habitaciones las probabilidades se estabilizan. He calculado el valor al que convergen para infinitas habitaciones: 0,154700538, 0,309401077, 0,082903769, 0,022213998, 0,005952223,… pero no sé de dónde salen estos valores de forma teórica.


De: Juan Carlos
2012-05-14 22:04:02

Y si en lugar de morir los 2/3, son éstos los que sobreviven (es decir, de las tres habitaciones, solo una te aniquila)??


De: Pableras
2012-05-15 11:33:15

Lo mas cruel de todo es que, sin entrar a pensarlo demasiado, creo que (corregidme si me equivoco)... Todos los que hemos dado con la solución ¡¡tendríamos mas probabilidades de morir que aquellos que se equivocaron!!


De: quake595
2012-05-15 12:51:21

ok pedro duda resuelta

gracias^^


De: Argus
2012-05-15 14:49:12

Mmonchi, vaya despliegue. Eso es lo que iba yo buscando exactamente.

Juan Carlos, si muere 1/3 cada vez, la fracción de muertes es 1/3, 2/9, 4/27, 8/81,..., que suma también 1.


De: txuripoket
2012-05-16 09:20:28

hola:
no se si he pillado bien la logica del problema para n puertas si n tiende a infinito, corregidme si me equivoco, pero, si los alienigenas te pillan con las manos en los bolsillos, sin papel ni lapiz, ni calculadora, podriamos deducir lo siguiente???

lo mas probable es q muera en la puerta 2 o la puerta n, con una probabilidad de poco mas del 50%, 25% cada uno, si se sobrevive, lo mas probable es q muera en la puerta1, con una probabilidad de poco mas de 1/8, y luego q muera en la puertas 3 y n-1, con una probabilidad de poco mas de 1/16 cada una, y segun nos alejamos de las puertas 2 y n, nuestra probabilidad baja cada vez mas, vamos, q a la puerta 200 no llega ni blas...
imagino q el objeto de estos desafios no es ser tan chapucero, pero hace mas de 20 años q deje las matematicas y me cuesta hacerlo bien y bonito, asi q por ahora me conformo con entenderlo...


De: alb.
2012-05-16 10:20:09

Mmonchi

"He calculado el valor al que convergen para infinitas habitaciones: 0,154700538, 0,309401077, 0,082903769, 0,022213998, 0,005952223,… pero no sé de dónde salen estos valores de forma teórica."

Pues no lo se... pero intuyo que es la superposición de dos campanas de Gauss.


De: txuripoket
2012-05-16 13:02:59

alb.

podrias explicar q es una superposicion de dos campanas de gauss?


De: Argus
2012-05-16 15:17:41

Para el caso de infinitas habitaciones se puede calcular por triángulos de Pascal. Es difícil explicarlo en un comentario.

En una cuadrícula voy a poner las probabilidades de "estar" en cada habitación. Las columnas son las habitaciones y las filas son los turnos. Empezamos por la fila de abajo (turno 0) con un 1 en el centro (columna de la habitación inicial). En el primer turno (segunda fila de la cuadrícula) tenemos 1/2, 0, 1/2, es decir, la mitad en cada habitación contigua y 0 en la habitación original. En el segundo paso (tercera fila de la cuadrícula) ponemos 1/4, 0, 2/4, 0, 1/4, es decir, vamos formando un triángulo invertido con las probabilidades de encontrarnos en cada habitación.

Los numeradores son los valores del triángulo de Pascal y los denominadores son potencias de 2. Además, como hay ceros intercalados tenemos que las habitaciones pares tienen como denominador las potencias pares de 2 y las habitaciones impares tienen como denominador las potencias impares de 2.

Esto son las probabilidades de estar en cada habitación en cada turno (columna y fila) y hay que multiplicarlas por la probabilidad de morir en ese turno, que es 1/(2elevado a turno).

Poniéndolo en una serie, la probabilidad de morir en la habitación inicial sería: 2/16 + 6/256 + 20/4096 +...

La probabilidad de morir en la contigua sería: 1/4 + 3/16 + 10/1024 + 35/16384 + ...

Desconozco el término general de las series porque no sé el término general de los valores del triángulo de Pascal, pero con unas cuantas iteraciones los resultados son coherentes con lo que propone Mmonchi.

Bueno, un lío explicarlo, perdón pero quería intentarlo.


De: Karlo
2012-05-17 16:30:48

Argus, yo también estuve haciendo para infinitas habitaciones y me salió los triángulos de pascal. Pero hubo una catástrofe informática y se me borró todo XD así que me dio pereza rehacerlo. Eso si, salía un problema muy bonito aunque con unas sumas horribles.


De: patriot
2012-05-18 16:17:05

a mi me encantó el relato de J, me sacó carcajadas. palmas, palmas...


De: patriot
2012-05-18 16:19:15

y el simulador está muy interesante, algo que noté fue que sin importar el número de habitaciones, siempre la última es de las que tiene más posibilidades.


De: Mmonchi
2012-05-20 19:35:39

He calculado la probabilidad de morir en la habitación n si hay 2m-1 o 2m-2 habitaciones (son impares o pares). La numeración de las habitaciones empieza por la más alejada (o las dos más alejadas si son impares) que es la 1 y va aumentando hasta llegar a la habitación inicial, que es la m. Por ejemplo, las habitaciones del problema original serían 1 (la C), 2 (la B y la D) y 3 (la A) con m=3 (2*3-2=4 habitaciones).

Llamo P(x,y) a la probabilidad de morir en la habitación x si hay y habitaciones. En el caso par:
P(n,2m-2)=((2-√3)(2+√3)^n+(2+√3)(2-√3)^n)/((3/2+√3)(2+√3)^(m-2)+(3/2-√3)(2-√3)^(m-2)) si n es menor que m y P(m,2m-2)=P(m-1,2m-2)/2 cuando n=m.

En el caso impar:

P(n,2m-1)=((1-1/√3)(2+√3)^n+(1+1/√3)(2-√3)^n)/((5/2+9/2√3)(2+√3)^(m-2)+(5/2-9/2√3)(2-√3)^(m-2)) si n es menor que m y P(m,2m-2)=P(m-1,2m-2)/2 cuando n=m.

Para calcularlo he hallado el término general de forma similar a como se calcula el término n-simo de la sucesión de Fibonacci. :-)


De: Manuko
2012-06-05 03:22:55

Lo de "bípedo implume" me llegó al alma... jajajajajajaja, buenísimo.


De: Adrián
2012-06-24 06:18:03

:( iba bien yo... llegue al 66% en B-D y 33% en A-C, debido a que B-D son lo mismo y A-B también entonces el problema se puede ver como si solo tuviera 2 habitaciones (pertenecería al grupo de soluciones recursivas) por lo tanto seria lo mismo que moverse solamente entre A y B... pero en la letra del ejercicio decía:

"No vale, por ejemplo, moverte siempre entre A y B y decir que hay un 25% de probabilidades de morir en A y un 75% de morir en B"

por lo que creí que en algo le estaba errando sino debería decir 33% en A y 66% en B...
En fin, al menos lo hubiera resuelto bien


Escribe un comentario

Todos los comentarios deben ser aprobados por un moderador antes de ser publicados. Si quieres puedes usar markdown. Todos los campos son opcionales excepto el cuerpo del comentario, claro:

Nombre:
E-mail: (privado, para que aparezca tu gravatar)
Sitio web:

« El Sistema Solar - Saturno (II) [Mecánica Clásica I] Energía potencial »