jueves, 28 de febrero de 2013

1091 - Otro de sombreros II

Este problema es exactamente igual al anterior "otro problema de sombreros" pero con la diferencia de que los presos no saben si el anterior habló o no.

Existe una estrategia que permite salvarse en el 90% de los casos



  Hacer click aquí para ver la solución 
Si lo quieres compartir o guardar
Share/Bookmark

6 comentarios:

  1. Con 3 presos consigo salvarlos un 75% de las veces. El sistema es que el preso que vea dos sombreros iguales diga el color contrario y si no, pase. Con tres sombreros hay 8 casos posibles:

    BBB: los tres dicen NEGRO: mueren.
    BBN: los dos de sombrero blanco pasan y el del sombrero negro dice NEGRO: se salvan.
    BNB: los dos de sombrero blanco pasan y el del sombrero negro dice NEGRO: se salvan.
    NBB: los dos de sombrero blanco pasan y el del sombrero negro dice NEGRO: se salvan.
    BNN: los dos de sombrero negro pasan y el del sombrero blanco dice BLANCO: se salvan.
    NBN: los dos de sombrero negro pasan y el del sombrero blanco dice BLANCO: se salvan.
    NNB: los dos de sombrero negro pasan y el del sombrero blanco dice BLANCO: se salvan.
    NNN: los tres dicen BLANCO: mueren.

    Se salvan 6 de 8 veces, un 75%.

    Voy a tratar de extrapolarlo a más presos.

    ResponderEliminar
  2. Exacto Mmonchi, esa es la solución para tres personas que da el libro. Para mas gente tienes que buscar una estrategia similar a esta en la cual cuando se equivoca uno, se equivocan todos, y si no, uno solo acierta, si nadie da con la respuesta pondré "pistas".

    ResponderEliminar
  3. No encuentro una estrategia similar para 4 presos, es más, creo que no existe. Para 5 tampoco la he encontrado, y para 6 lo mejor que consigo es dividirles en dos grupos de 3. Voy a probar con 7 después de comer, a ver si se me ocurre algo.

    ResponderEliminar
    Respuestas
    1. Las mejores respuestas se logran cuando los presos son 2^n y se salvan el (2^n -1) / 2^n % de las veces

      Eliminar
  4. Voy a suponer que existe una solución óptima para N presos. Hay 2^N formas de colocarles los sombreros. Llamo F al número de formas en las que fallo: el óptimo se consigue cuando en los fallos fallan todos los presos y en los aciertos acierta uno y el resto pasan. El total de fallos es FxN y el de aciertos (2^N-F)x1. Como la probabilidad de acertar o fallar es la misma, el número de fallos es igual al de aciertos: FxN=2^N-F. Despejando, la probabilidad de acertar es N/(N+1) y la de fallar 1/(N+1).

    Pero para llegar al óptimo F debe ser entero: F=2^N/(N+1). Como el numerador es una potencia de 2, el denominador también debe serlo. Eso solo es posible si N+1=2^k, es decir, N=2^k-1. Por tanto solo encontraremos la solución óptima es los casos en los que el número de presos sea 3, 7, 15, 31...

    ¿Y en qué consiste esa solución? En que de los escenarios que se le pueden presentar a cada preso, que son 2^(N-1), eligen 2^(N-k) en los que contestan y en el resto pasan. Se debe cumplir que en 2^(N-k) formas de colocarlos estén todos esos escenarios y en el resto haya uno y solo uno. Además, cuando fallen, lo deben hacer en las 2^(N-k) formas del principio y cuando acierten lo deben hacer en las demás.

    Para k=2, N=2^2-1=3, el número de formas es 2^3=8, fallan en F=2^3/(3+1)=2 y aciertan en 8-2=6. Los escenarios posibles son 2^(3-1)=4 (BB, BN, NB y NN, lo que ve cada preso) y eligen 2^(3-2)=2 en los que contestar (BB y NN) y 4-2=2 en los que pasar (BN y NB). En dos escenarios están siempre los dos primeros (BBB y NNN) y en los otros 6 solo están una vez (BBN, BNB, BNN, NBB, NBN y NNB), de modo que hay 6 aciertos y 6 fallos y la probabilidad de salvarse es 3/4.

    Hasta aquí funciona la teoría. Con 7 presos debo identificar los 16 escenarios en los que contestar, y qué decir en cada uno, y los 48 en los que pasar; con 15 presos se debe contestar en 2048 escenarios y pasar en 14336...

    Ahora solo falta encontrar un método para encontrar esos escenarios y lo que se debe decir. Naturalmente, dando por hecho que la solución existe. ;-)

    ResponderEliminar
    Respuestas
    1. La solución esta relacionada con los números binarios y el juego del nim...

      Eliminar

Si quieres deja un comentario, si la entrada tiene mas de 15 dias deberás esperar a que la autorice y por favor si no tienes gmail deja tu nombre si no quedas como anónimo. Gracias!