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 ]
Esteban Dimitroff Hódi

Posts: 21
Registered: 4/27/09
Re: [Snark] Sol: Otro de presos.
Posted: Feb 18, 2013 11:08 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply
att1.html (9.4 K)

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




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.