Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » Math Topics » Snark

Topic: Re: [Snark] Sol: Otro de presos.
Replies: 14   Last Post: Feb 18, 2013 1:06 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
German Zorba

Posts: 376
From: Argentina
Registered: 9/5/06
Re: [Snark] Sol: Otro de presos.
Posted: Feb 18, 2013 12:31 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply
att1.html (12.2 K)

Estaba escribiendo un mensaje hablando sobre las estrategias fijas, pero
después del comentario de esteban lo descarté y paso al problema del
cálculo de probabilidades de sobrevivir con el método propuesto por él.

El truco de cálculo consiste en pensar a la permutación descompuesta en
ciclos. (Un ciclo es una secuencia de la forma: la tarjeta 1 está en la
posición, 10, la tarjeta 10 está en la posición 3, la tarjeta 3 en la
posición 27 y la tarjeta 27 en la posición 1, este es un ciclo de longitud
4, una tarjeta que está en su misma posición es un ciclo de longitud 1).

Usando el método, cada uno encuentra su tarjeta si está en un ciclo de a lo
sumo longitud 50. La probabilidad individual de estar en un ciclo de
longitud 50 es 50%, con lo cual no hay mejora por ese lado, pero cuando
alguien encuentra su tarjeta, la probabilidad condicional de los otros
aumenta, porque los que estaban en el mismo ciclo también van a hallar su
tarjeta, y los que no tienen menos tarjetas de las que tomar.

Para calcular bien cuál es la mejora, es más sencillo calcular la
probabilidad de morir: los presos morirán si hay algún ciclo de más de 50.
La probabilidad de que haya un ciclo de longitud 50+k puede calcularse de
manera sencilla, y después de un par de pasos algebraicos se puede
simplificar para obtener 1/(50+k).

Entonces la probabilidad de sobrevivir es 1 - 1/51 - 1/52 - 1/53 - ... -
1/100. Esta suma no es tan difícil de calcular con una computadora, pero
para hacerlo a mano, usando herramientas de Cálculo I, la podemos acotar
entre 1 - ln(100/50) y 1-ln(101/51), que calculadora mediante da entre
30,685 % y 31,67%.

No sé si es la mejor estrategia, pero sí es una mejora realmente
importante.

Nota: lo que me puso en tema fue el aporte de Jesús, diciendo que para 4
las que funcionaban eran las permutaciones de orden 1 y 2. No es el orden
de la permutación en sí lo que define, sino los órdenes de los ciclos, pero
estaba cerca.

Saludos,

Germán

2013/2/18 Esteban Dimitroff Hódi <estebandh@gmail.com>

> Je, revisando un poco esto me dio risa mi comentario inocente de "mi
> programa calcula por fuerza bruta, asi que se queda sin memoria al intentar
> calcular para 100 presos".
>
> Lo gracioso de eso es que es bastante facil corregir el programa para que
> no utilice masivamente la memoria (si alguien le interesa lo explico mas
> abajo). Pero lo definitivamente prohibitivo es el tiempo de ejecucion. Mi
> computadora evalua aproximadamente 100000 (cien mil) permutaciones por
> segundo. Supongamos que consiga una maquina un poquito mas rapida (o logre
> optimizar mi algoritmo)... digamos 1000 veces mas rapida. Asi lograria
> evaluar 100 millones de permutaciones por segundo. Para evaluar las 100!
> permutaciones, a dicha computadora le llevara nada menos que (2,959...) × 10
> 142 años, que se me hace un poco mucho para dedicarle solo a este
> problema... Si quieren una comparacion, segun wikipedia la edad del
> universo es de (13,7 ± 0,2) × 109 años.
>
> Asi que deberemos calcular la probabilidad final por metodos analiticos,
> evidentemente...
>
> Saludos,
>
> Esteban
>
>
> NB: Para resolver el tema de la memoria es sencillo: Yo calculaba la
> totalidad de las permutaciones y luego evaluaba una por una. Para
> cantidades chicas de presos (hasta 10) era mas o menos tolerable, pero no
> escalaba. Para no depender de la memoria, puedo generar cada permutacion,
> evaluarla, utilizarla para generar la siguiente y descartarla, manteniendo
> un contador de exitos. De esta manera la memoria ocupada sera solamente el
> valor de este contador, mas el tamaño que ocupe la permutacion actual
> siendo evaluada (una lista de 100 elementos).
>
>
> 2013/2/18 Jesus Sanz <jesanz47@yahoo.es>
>

>> Pues si, después de probar estrategias fijas que evidentemente no
>> funcionan, probé la idea de usar en segundo lugar el sobre de numero
>> correspondiente al del preso que aparece al abrir el primer sobre, no solo
>> para el primer preso sino para todos, y parece que si funciona, incluso
>> para más presos como veo que ha comprobado Esteban. Aunque no entiendo muy
>> bien porqué.
>> El número de aciertos sigue siendo el mismo, pero con esta estrategia no
>> hay posibilidad de acertar 2 ni 3 veces, solo 0, 1 o 4. Con lo cual
>> aparecen los 10 casos favorables a cuatro aciertos, correspondientes a
>> 1,2,3,6,7,8,15,17,22 y 24 de los 24 casos posibles ordenados.
>> Y tratando de ver algo más, consulto la Encyclopedia of Integer
>> Sequences, y allí está la A066646:
>>
>> *1*, *2*, *3*, *6*, *7*, *8*, *15*, *17*, 22, 24, 25, 26 ......
>> Arrange the permutations of {1...m} in lexicographic order. Sequence
>> gives indices of permutations of orders 1 and 2.
>> ¿?
>>
>> Seguiré tratando de entender porqué funciona. Muy buen problema, Paco, y
>> totalmente de acuerdo con lo de "increíble, pero cierto".
>>
>> Un cordial saludo,
>>
>> Jesús Sanz
>>
>>
>>
>> *De:* Paco Moya <pacomoyao@gmail.com>
>> *Para:* Jesus Sanz <jesanz47@yahoo.es>; Lista de Juegos de Ingenio <
>> snark@ccc.uba.ar>
>> *Enviado:* Domingo 17 de febrero de 2013 21:49
>>
>> *Asunto:* Re: [Snark] Sol: Otro de presos.
>>
>> Hola a todxs.
>>
>> El día 16 de febrero de 2013 21:44, Jesus Sanz <jesanz47@yahoo.es>
>> escribió:

>> > Entiendo que:
>> >
>> > - El primer preso tiene una información adicional: al abrir cada sobre,
>> > encuentra el nombre de un preso determinado. Y puede usar esa

>> informacion
>> > para cambiar su estrategia. Pero no comunicarla.
>> > - Y cada preso a partir del segundo debe tener una estrategia fija, que
>> > supone que los anteriores han debido tener éxito (si no, ya da igual).
>> >
>> > Lo cual no me ayuda nada con la solución.
>> >
>> > Un cordial saludo,
>> >
>> > Jesús Sanz

>>
>> No hay información adicional de ningún tipo.
>> Poned las 24 permutaciones de 4 elementos y haced que todos acierten
>> 10 de entre ellas. Increíble pero cierto.
>> Paco Moya.
>>
>>

>> > Hola a todxs.
>> > Vamos a simplificar un "poco". Si hubiese 4 presos y 4 sobres existe
>> > un procedimiento para que la probabilidad de salvarse sea de 10/24,
>> > casi el 42%. Es una pista.
>> > Paco Moya
>> >
>> >
>> > _______________________________________
>> > Snark
>> > Más información en http://www.snarkianos.com/
>> > http://mailman.uba.ar/mailman/listinfo/snark
>> >
>> >

>>
>>
>>
>> _______________________________________
>> Snark
>> Más información en http://www.snarkianos.com
>> http://mailman.uba.ar/mailman/listinfo/snark
>>
>>
>>

>
> _______________________________________
> Snark
> Más información en http://www.snarkianos.com
> http://mailman.uba.ar/mailman/listinfo/snark
>
>
>

_______________________________________
Snark
Más información en http://www.snarkianos.com
http://mailman.uba.ar/mailman/listinfo/snark




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.