|
|
Re: [Snark] Sol: Otro de presos.
Posted:
Feb 18, 2013 12:49 PM
|
|
|
|
Je si. El aporte de Jesus me dio una doble pista:
Por un lado, me puse a leer de permutaciones, ciclos y ordenes, hasta
terminar en que solo seran exitosos con mi estrategia en aquellas
permutaciones donde no haya ciclos con longitud mayor a 50.
Por otro lado, al saber de la existencia de dicha enciclopedia, ingrese el
mumero de permutaciones exitosas que obtuve para el ejemplo con 10 presos,
y ahi estaba, la formula que andaba necesitando para calcular la
probabilidad final (ademas de un link al problema y su solucion :$ )
Aqui: http://oeis.org/search?q=1285920&language=english&go=Search
La formula, finalmente para la probabilidad con n presos es 1/2 - 1/3 + 1/4
-..... c/n donde c = (-1)n
y para 100 presos me da exactamente 31.182782068980487% y a medida que
aumentan los presos desciende hasta el limite con 1-ln(2) como calculo
German.
Saludos,
Esteban
2013/2/18 German Zorba <germanzorba@gmail.com>
> 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
>
>
>
_______________________________________
Snark
Más información en http://www.snarkianos.com
http://mailman.uba.ar/mailman/listinfo/snark
|
|
