Pongo aquí la solución para la entrada
1091 otro problema de sombreros II
Pensemos en primer lugar la mejor táctica para tres presos.
Las ocho posibles combinaciones son:
NNN
NN
R
N
RN
RNN
RRN
RN
RN
RRRRR
Estrategia para cada preso:
- Pasar, si los sombreros que ve son de distinto color
- Decir el color contrario cuando ve dos sombreros del mismo color
Usando esta estrategia se salvarian en 6 de los 8 casos (solo moririan si los 3 sombreros son del mismpo color) o sea que la probabilidad de salvarse es del 75%.
Hay que notar que en los casos en los que fallan, TODOS los presos arriesgan y TODOS se equivocan. Esto es fundamental para entender la estrategia, las seis veces que se equivocan entran en solo dos de las configuraciones, es decir que la única forma de acertar es que las predicciones equivocadas se usen con la misma configuración de sombreros.
Para n jugadores, lo ideal es duplicar este hecho y tener dos configuraciones,
- "Buena", en la cual solo un jugador arriesga y acierta, y
- "Mala", aquella en la que todos arriesgan y todos se equivocan,
si esto se da la probabilidad de ganar es n/n+1.
Esta configuracion óptima solo se logra si n+1 divide el total de las configuraciones 2^n, lo que indica que n debe ser uno menos que la potencia de 2.
Veamos el ejemplo de 15 presos, se le asigna a cada uno de ellos un número binario :
0001 0010 0011 0100
0101 0110 0111 1000
1001 1010 1011 1100
1101 1110 1111
Es importante entender que estas etiquetas se tratan como "nimbers" y no como números, es decir que cuando se los suma, se lo hace
sin acarreo, o sea que si la cantidad de unos en la columna es par la suma da cero, y si es impar da uno.
Ejemplos:
0010 0001
1110 + 1111 +
1010 1010
------ ------
0110 0100
Las malas configuraciones se daran en los casos en que la suma de las etiquetas de los que tienen sombreros rojos da 0000.La estrategia es la siguiente :
- Cada preso suma las etiquetas de los que tienen puesto sombreros rojos
- Si la suma le da 0000, debe arriesgar que él mismo tiene sombrero rojo
- Si en cambio la suma le da su propio número, arriesgará que tiene puesto un sombrero negro
- Si la suma no le da 0000 ni su propio número, pasará.
Porque funciona?
Supongamos que la suma de los sombreros rojos da efectivamente 0000.
En este caso a todos los que tienen sombreros negros, la suma les dará 0000 y arriesgaran que tienen puestos sombreros rojos, en tanto que a los que tienen puestos sombreros rojos la suma les dará su propio número y arriesgaran que tienen puesto un sombrero negro.
Es decir que
todos los presos arriesgan y todos se equivocan!
En cualquier otro caso, por ejemplo si la suma de los sombreros rojos diera 0101, el único preso que arriesgará es el que tiene el número 0101 y acertará.
Es importante notar que la suma puede dar 0101, teniendo el preso con la etiqueta 0101 un sombrero rojo o un sombrero negro y que en ambos casos acertará:
Ejemplo en el que la suma da 0101 y el que tiene dicha etiqueta tiene un sombrero rojo:
0101
0100
0110
0010------
0101
En este caso los que tienen sombreros negros pasaran ya que ninguno tiene la etiqueta 0101, en tanto que el que lo tiene es el único al que la suma le da 0000 (y por lo tanto dirá rojo y acertará):
El ve :
0100
0110 +
0010
-----
0000
Ejemplo en el que el preso que tiene el 0101 tiene sombrero negro y la suma de los que tienen sombreros rojos da 0101
0001
0110
0010
-----
0101
En este caso el que tiene la etiqueta 0101 dirá que tiene sombreo negro y acertará , los que tienen sombrero rojo la suma no les de en ningun caso 0000
La probabilidad de que la suma de los sombreros rojos de 0000 es exactamente 1/16 (hay 16 sumas posibles), entonces la estrategia gana con una probabilidad de 15/16
Si lo quieres compartir o guardar
1094 - Solución a la entrada 1091