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
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
Existe una estrategia que permite salvarse en el 90% de los casos
Hacer click aquí para ver la solución
Suscribirse a:
Enviar comentarios (Atom)
Entradas
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:
ResponderEliminarBBB: 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.
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".
ResponderEliminarNo 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.
ResponderEliminarLas mejores respuestas se logran cuando los presos son 2^n y se salvan el (2^n -1) / 2^n % de las veces
EliminarVoy 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).
ResponderEliminarPero 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. ;-)
La solución esta relacionada con los números binarios y el juego del nim...
Eliminar