martes, 5 de marzo de 2013

1094 - Solución a la entrada 1091

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
NNR
NRN
RNN
RRN
RNR
NRR
RRR

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
Share/Bookmark

1 comentario:

  1. Creo que se pueden dar por muertos... :-D

    Siempre me he preguntado cómo se le puede ocurrir esto a alguien. No el hecho de resolverlo cuando te lo plantean, que también es complicado, sino lo de resolver algo que aparentemente no tiene solución y además es muy difícil de encontrar. Genial el problema.

    ResponderEliminar

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!