Los acertijos de inducción son acertijos lógicos , que son ejemplos de razonamiento de múltiples agentes , donde la solución evoluciona junto con el principio de inducción . [1] [2]
El escenario de un rompecabezas siempre involucra a varios jugadores con la misma capacidad de razonamiento, que siguen los mismos pasos de razonamiento. Según el principio de inducción, una solución al caso más simple hace obvia la solución del siguiente caso complicado. Una vez resuelto el caso más sencillo del rompecabezas de inducción, posteriormente se resuelve todo el rompecabezas.
Las características reveladoras típicas de estos acertijos incluyen cualquier acertijo en el que cada participante tiene una determinada información (generalmente como conocimiento común ) sobre todos los demás participantes pero no sobre ellos mismos. Además, normalmente se da algún tipo de pista para sugerir que los participantes pueden confiar en la inteligencia de los demás: son capaces de hacer teoría de la mente (que "todos los participantes conocen el modus ponens " es de conocimiento común). [3] Además, la inacción de un participante es una comunicación no verbal de la falta de conocimiento de ese participante, que luego se convierte en conocimiento común para todos los participantes que observaron la inacción.
El rompecabezas de los niños fangosos es el rompecabezas de inducción que aparece con más frecuencia en la literatura científica sobre lógica epistémica . [4] [5] [6] El rompecabezas de niños fangosos es una variante de los conocidos rompecabezas de hombres sabios o esposas/maridos infieles. [7]
Los rompecabezas de sombreros son variaciones de rompecabezas de inducción que se remontan a 1961. [8] En muchas variaciones, los rompecabezas de sombreros se describen en el contexto de los prisioneros. [9] [10] En otros casos, los acertijos de sombreros se describen en el contexto de los reyes magos. [11] [12]
A un grupo de niños atentos le dicen que algunos de ellos tienen la cara embarrada. Cada niño puede ver las caras de los demás, pero no puede decir si su propia cara está embarrada. A los niños se les dice que aquellos con la cara embarrada deben dar un paso adelante, pero cualquier niño con la cara limpia que dé un paso adelante será castigado. A la cuenta de tres, todo niño que crea que tiene la cara embarrada debe dar un paso adelante simultáneamente; cualquier niño que haga señales a otro de cualquier forma será castigado. Si algún niño con la cara embarrada no ha dado un paso adelante, se repetirá el proceso. [4] [5] [13]
Suponiendo que cada niño tiene (y sabe que cada uno de los demás tiene) una lógica perfecta, todos los niños con caras embarradas ( ) darán un paso adelante juntos por turno . Los niños tienen información diferente, dependiendo de si su propia cara está embarrada o no. Cada miembro ve caras embarradas y sabe que esos niños darán un paso adelante por turno si son los únicos con caras embarradas. Cuando eso no ocurre, cada miembro de sabe que también es miembro de y da un paso adelante por turno . Cada uno de los que no son miembros ve caras embarradas y no esperarán que nadie dé un paso adelante hasta que al menos se dé la vuelta .
Supongamos que hay dos hijos, Alice y Bob, y que solo Alice está embarrada ( ). Alice sabe que "algunos" niños tienen la cara embarrada pero que la cara de nadie más está embarrada, lo que significa que su propia cara debe estar embarrada y da un paso adelante en la curva uno. Bob, al ver la cara embarrada de Alice, no tiene forma de saber en el turno uno si su propia cara está embarrada o no hasta que Alice da un paso adelante (lo que indica que su propia cara debe estar limpia). Si tanto Alice como Bob están sucios ( ), cada uno está en la posición de Bob cuando : ninguno puede dar un paso adelante en el turno uno. Sin embargo, en el turno dos, Bob sabe que Alice debe haber visto que su cara está embarrada (porque ella no dio un paso adelante en el turno uno), por lo que da un paso adelante en el turno dos. Usando la misma lógica, Alice también da un paso adelante en el turno dos.
Supongamos que hay un tercer hijo, Charlie. Si Alice está embarrada ( ), no verá caras embarradas y dará un paso adelante en el turno uno. Si tanto Alice como Bob están embarrados ( ), ninguno puede dar un paso adelante en el turno uno, pero en el turno dos sabrán que el otro vio una cara embarrada (que pueden ver que no es la de Charlie), por lo que su propia cara debe estar embarrada y ambos Da un paso adelante en la curva dos. Charlie, al ver dos caras embarradas, no sabe en la curva dos si su propia cara está embarrada o no hasta que Alice y Bob dan un paso adelante (lo que indica que su propia cara está limpia). Si los tres están embarrados ( ), cada uno está en la posición de Charlie cuando : cuando dos personas no dan un paso adelante en el turno dos, cada uno sabe que el otro ve dos caras embarradas, lo que significa que su propia cara debe estar embarrada, y cada uno da un paso adelante. en la curva tres.
Se puede comprobar que los niños embarrados darán un paso adelante en su turno . [4] [14]
Los rompecabezas de niños embarrados también se pueden resolver utilizando la inducción hacia atrás de la teoría de juegos . [13] El rompecabezas de niños fangosos se puede representar como un juego de forma extensiva de información imperfecta . Cada jugador tiene dos acciones: quedarse atrás y dar un paso adelante. Hay un movimiento natural al inicio del juego, que determina los niños con y sin cara embarrada. Los niños no se comunican como en los juegos no cooperativos . Cada golpe es un movimiento simultáneo de los niños. Es un juego secuencial de duración ilimitada. La solución de la teoría de juegos necesita algunos supuestos adicionales:
Si Alice está confusa, la última suposición hace que sea irracional que ella dude. Si Alice y Bob están embarrados, Alice sabe que la única razón de Bob para quedarse atrás después del primer golpe es el temor a recibir el gran castigo de dar un paso adelante sin la cara embarrada. En el caso de niños embarrados, recibir veces la penalización menor sigue siendo mejor que la penalización grande.
El Rey convocó a su corte a los tres hombres más sabios del país para decidir quién sería su nuevo consejero. Colocó un sombrero en cada una de sus cabezas, de modo que cada sabio pudiera ver todos los demás sombreros, pero ninguno de ellos pudiera ver el suyo. Cada sombrero era blanco o azul. El rey dio su palabra a los magos de que al menos uno de ellos llevaba un sombrero azul; es decir, podría haber uno, dos o tres sombreros azules, pero no cero. El rey también anunció que la contienda sería justa para los tres hombres. A los magos también se les prohibió hablar entre ellos. El rey declaró que el hombre que se levantara primero y anunciara correctamente el color de su sombrero se convertiría en su nuevo consejero. Los sabios se sentaron durante mucho tiempo antes de que uno se levantara y anunciara correctamente la respuesta. ¿Qué dijo y cómo lo resolvió?
Los Reyes Magos es uno de los acertijos de inducción más sencillos y uno de los indicadores más claros del método utilizado.
Como debe haber tres sombreros azules, el primer hombre que se dé cuenta se levantará y dirá azul.
Solución alternativa: Esto no requiere la regla de que la contienda sea justa para cada uno. Más bien se basa en el hecho de que todos son hombres sabios y que les lleva algún tiempo llegar a una solución. Sólo puede haber tres escenarios: un sombrero azul, dos sombreros azules o tres sombreros azules. Si solo hubiera un sombrero azul, entonces el portador de ese sombrero vería dos sombreros blancos y rápidamente sabría que tiene que tener un sombrero azul, por lo que se levantaría y anunciaría esto de inmediato. Como esto no ha sucedido, entonces debe haber al menos dos sombreros azules. Si hubiera dos sombreros azules, entonces cualquiera de los que llevaban un sombrero azul miraría hacia el otro lado y vería un sombrero azul y un sombrero blanco, pero no sabría el color de su propio sombrero. Si el primer portador del sombrero azul asumiera que tenía un sombrero blanco, sabría que el otro portador del sombrero azul estaría viendo dos sombreros blancos y, por lo tanto, el segundo portador del sombrero azul ya se habría levantado y anunciado que llevaba un sombrero azul. Por lo tanto, dado que esto no ha sucedido, el primer usuario del sombrero azul sabría que está usando un sombrero azul y podría levantarse y anunciarlo. Dado que uno o dos sombreros azules son tan fáciles de resolver y nadie se ha levantado rápidamente, entonces todos deben llevar sombreros azules.
En el Reino de Josefina toda mujer tiene que aprobar un examen de lógica antes de poder casarse. [15] Toda mujer casada conoce la fidelidad de todos los hombres del Reino excepto su propio marido, y la etiqueta exige que a ninguna mujer se le informe sobre la fidelidad de su marido. Además, un disparo disparado en cualquier casa del Reino se escuchará en cualquier otra casa. La reina Josefina anunció que se había descubierto al menos un hombre infiel en el Reino, y que cualquier mujer que supiera que su marido era infiel debía dispararle a la medianoche siguiente al día siguiente de descubrir su infidelidad. ¿Cómo lograron esto las esposas?
El problema de Josephine es otro buen ejemplo de un caso general.
Este problema también se conoce como el problema de los maridos infieles, el problema de las esposas infieles y el problema de los niños fangosos. Es lógicamente idéntico al Problema de los Ojos Azules .
Este problema también aparece como un problema que involucra sombreros negros y sombreros blancos en el clásico libro de texto de CL Liu 'Elementos de matemáticas discretas'. [ cita necesaria ]
En la Convención Secreta de Lógicos, el Maestro Lógico colocó una banda en la cabeza de cada asistente, de modo que todos los demás pudieran verla pero la persona misma no. Había muchos colores diferentes de banda. Todos los Lógicos se sentaron en círculo, y el Maestro les ordenó que debían tocar una campana en el bosque a intervalos regulares: en el momento en que un Lógico supiera el color de su frente, debía irse al sonar la siguiente campana. Se les indicó que no hablaran, ni usaran un espejo o una cámara, ni que evitaran usar la lógica para determinar el color de su banda. En caso de que algún impostor se hubiera infiltrado en la convención, cualquiera que no saliera a tiempo sería eliminado bruscamente en el momento correcto. De manera similar, cualquiera que intentara salir temprano sería retenido bruscamente en su lugar y retirado en el momento correcto. El Maestro tranquilizó al grupo afirmando que el rompecabezas no sería imposible para ningún verdadero lógico presente. ¿Cómo lo hicieron? [dieciséis]
Alicia en la convención de Lógicos es inducción general más un salto de lógica.
Varios jugadores llevan cada uno un sombrero, que puede ser de varios colores específicos. Los jugadores pueden ver los colores de al menos las gorras de otros jugadores, pero no los suyos. Con comunicación muy restringida o nula, algunos de los jugadores deben adivinar el color de su sombrero. El problema es encontrar una estrategia para que los jugadores determinen los colores de sus sombreros en función de los sombreros que ven y de lo que hacen los demás jugadores. En algunas versiones, compiten por ser el primero en adivinar correctamente; en otros, pueden elaborar una estrategia de antemano para cooperar y maximizar la probabilidad de acertar. [17]
Una variación recibió cierta publicidad nueva como resultado del doctorado de Todd Ebert en 1998. tesis en la Universidad de California, Santa Bárbara . [18] Es una pregunta de estrategia sobre un juego cooperativo , que tiene conexiones con la teoría de la codificación algebraica . [19]
A tres jugadores se les dice que cada uno de ellos recibirá un sombrero rojo o un sombrero azul. Deben levantar la mano si ven un sombrero rojo en otro jugador mientras están parados en círculo uno frente al otro. Gana el primero que adivine correctamente el color de su sombrero.
Los tres jugadores levantan la mano. Después de que los jugadores se hayan visto durante unos minutos sin adivinar, un jugador anuncia "Rojo" y gana. ¿Cómo lo hizo el ganador y de qué color son los sombreros de todos?
En primer lugar, si dos personas tuvieran sombreros azules, no todos habrían levantado la mano. A continuación, si el jugador 1 hubiera visto un sombrero azul en el jugador 2 y un sombrero rojo en el jugador 3, entonces el jugador 1 habría sabido inmediatamente que su propio sombrero debía ser rojo. Así, cualquier jugador que vea un sombrero azul podrá adivinarlo inmediatamente. Finalmente, el ganador se da cuenta de que, como nadie adivina a la vez, no debe haber sombreros azules, por lo que todos los sombreros deben ser rojos. [20]
En el caso en el que cada jugador tiene que adivinar, pero es libre de elegir cuándo hacerlo, existe una estrategia cooperativa que permite a cada jugador adivinar correctamente a menos que todos los sombreros sean del mismo color. Cada jugador debe actuar de la siguiente manera:
Supongamos que en total hay B sombreros azules y R sombreros rojos. Hay tres casos.
Si B = R , entonces los jugadores que usan sombreros azules ven B-1 sombreros azules y B sombreros rojos, así que espere B -1 segundos y luego adivine correctamente que están usando un sombrero azul. De manera similar, los jugadores que usan un sombrero rojo esperarán R −1 segundos antes de adivinar correctamente que llevan un sombrero rojo. Así, todos los jugadores aciertan al mismo tiempo.
Si B < R , entonces aquellos que usen un sombrero azul verán B −1 sombreros azules y R sombreros rojos, mientras que aquellos que usen un sombrero rojo verán B sombreros azules y R −1 sombreros rojos. Como B −1 < B ≤ R −1, aquellos jugadores que lleven un sombrero azul serán los primeros en hablar, adivinando correctamente que su sombrero es azul. Luego, los demás jugadores adivinan correctamente que su sombrero es rojo.
El caso donde R < B es similar.
Según la historia, cuatro presos son arrestados por un delito , pero la cárcel está llena y el carcelero no tiene dónde meterlos. Finalmente se le ocurre la solución de darles un rompecabezas para que, si lo logran, puedan quedar libres, pero si fallan, serán ejecutados.
El carcelero sienta a tres de los hombres en fila. A mira a la pared, B mira a A y C mira a B y A. Se coloca a un cuarto hombre detrás de una mampara (o en una habitación separada). El carcelero les regala sombreros de fiesta a los cuatro hombres. Explica que hay dos sombreros rojos y dos sombreros azules, que cada prisionero lleva uno de los sombreros y que cada uno de los prisioneros sólo ve los sombreros que tiene delante, pero ni a sí mismo ni detrás de él. El cuarto hombre detrás de la pantalla no puede ver ni ser visto por ningún otro prisionero. No se permite ninguna comunicación entre los prisioneros.
Si algún prisionero puede descubrir qué color de sombrero tiene en su cabeza con un 100% de certeza (sin adivinar), debe anunciarlo y los cuatro prisioneros quedarán libres . Si algún prisionero sugiere una respuesta incorrecta, los cuatro prisioneros son ejecutados. El enigma consiste en encontrar cómo pueden escapar los prisioneros.
Los presos saben que sólo hay dos sombreros de cada color. Entonces, si C observa que A y B tienen sombreros del mismo color, C deduciría que su propio sombrero es del color opuesto. Sin embargo, si A y B tienen sombreros de diferentes colores, entonces C no puede decir nada. La clave es que el prisionero B, después de permitir un intervalo apropiado y saber lo que haría C, puede deducir que si C no dice nada, los sombreros de A y B deben ser diferentes; Si puede ver el sombrero de A, puede deducir el color de su propio sombrero.
Al igual que muchos acertijos de este tipo, la solución se basa en el supuesto de que todos los participantes son totalmente racionales e inteligentes para hacer las deducciones apropiadas.
Después de resolver este enigma, se puede obtener una idea de la naturaleza de la comunicación reflexionando si el silencio significativo del prisionero C viola la regla de "no comunicación" (dado que la comunicación generalmente se define como la "transferencia de información").
En esta variante hay 3 prisioneros y 3 sombreros. A cada prisionero se le asigna un sombrero al azar, ya sea rojo o azul. Cada persona puede ver los sombreros de otras dos personas, pero no el suyo. Siguiendo una señal, cada uno tiene que adivinar el color de su propio sombrero o pasar. Ganan la liberación si al menos una persona adivinó correctamente y ninguna adivinó incorrectamente (aprobar no es ni correcto ni incorrecto).
Este rompecabezas no tiene una estrategia ganadora del 100%, pero se puede ganar con un 75% de posibilidades. Al considerar los colores de los sombreros como bits, este problema se puede resolver utilizando la teoría de la codificación , por ejemplo con códigos Hamming . [21]
En una variante de este rompecabezas, los prisioneros saben que hay 2 sombreros negros y 2 sombreros blancos, y que hay una pared entre A y B, pero los prisioneros B, C y D pueden ver quién está frente a ellos, es decir, D ve. B, C y la pared, B ve la pared y C ve B y la pared. (A nuevamente no se puede ver y solo está ahí para usar uno de los sombreros negros.) ¿Cómo pueden deducir los colores de todos ellos sin comunicarse?
Hay dos casos: en el caso trivial, dos de los cuatro prisioneros llevan sombreros negros. Cada uno de los otros dos prisioneros puede ver que uno de ellos lleva el sombrero de otro color. En el caso no trivial, dos de los cuatro prisioneros usan sombreros del mismo color, mientras que A y C usan sombreros negros. Después de un tiempo, los cuatro prisioneros deberían poder deducir que, debido a que D y B no pudieron indicar el color de su propio sombrero, A y C deben estar usando sombreros negros.
En otra variante, sólo intervienen tres prisioneros y cinco sombreros de colores conocidos (en este ejemplo, dos negros y tres blancos). Se ordena a los tres prisioneros que se coloquen en línea recta mirando hacia el frente, con A al frente y C detrás. Se les dice que habrá dos sombreros negros y tres sombreros blancos. Luego se pone un sombrero en la cabeza de cada prisionero; cada prisionero sólo puede ver los sombreros de las personas que tiene delante y no el suyo propio. El primer preso que sea capaz de anunciar correctamente el color de su sombrero será liberado. No se permite ninguna comunicación entre los prisioneros.
Supongamos que A usa un sombrero negro:
Entonces, si A usa un sombrero negro, habrá una respuesta bastante rápida de B o C.
Supongamos que A usa un sombrero blanco:
En este caso A, B y C permanecerían en silencio durante algún tiempo, hasta que A finalmente deduce que debe tener un sombrero blanco porque C y B han permanecido en silencio durante algún tiempo.
Como se mencionó, hay tres sombreros blancos y dos sombreros negros en total, y los tres prisioneros lo saben. En este acertijo, puedes asumir que los tres prisioneros son muy inteligentes y muy inteligentes. Si C no pudo adivinar el color de su propio sombrero es porque vio dos sombreros blancos o uno de cada color. Si hubiera visto dos sombreros negros, podría haber deducido que llevaba un sombrero blanco.
En esta variante hay 10 prisioneros y 10 sombreros. A cada prisionero se le asigna un sombrero al azar, ya sea rojo o azul, pero los prisioneros no conocen el número de cada color. Los prisioneros se alinearán en fila india donde cada uno pueda ver los sombreros delante de él pero no detrás. Comenzando con el prisionero al final de la fila y avanzando, cada uno debe, por turno, decir solo una palabra que debe ser "roja" o "azul". Si la palabra coincide con el color de su sombrero, son liberados; si no, los matan en el acto. Un guardia comprensivo les advierte de esta prueba una hora antes y les dice que pueden formular un plan en el que, siguiendo las reglas establecidas, 9 de los 10 prisioneros sobrevivirán definitivamente y 1 tiene una probabilidad de sobrevivir del 50/50. ¿Cuál es el plan para lograr el objetivo?
Los presos acuerdan que si el primer preso ve un número impar de sombreros rojos, dirá "rojo". De esta manera, los otros nueve prisioneros sabrán su propio color de sombrero después de que responda el prisionero detrás de ellos.
Como antes, hay 10 prisioneros y 10 sombreros. A cada prisionero se le asigna un sombrero al azar, ya sea rojo o azul, pero los prisioneros no conocen el número de cada color. Los prisioneros están distribuidos en la habitación de manera que puedan ver los sombreros de los demás pero no los suyos. Ahora, cada uno debe decir simultáneamente una sola palabra que debe ser "rojo" o "azul". Si la palabra coincide con el color de su sombrero, son liberados, y si suficientes prisioneros recuperan su libertad, pueden rescatar a los demás. Un simpático guardia les advierte de esta prueba una hora antes. Si pueden formular un plan siguiendo las reglas establecidas, 5 de los 10 prisioneros definitivamente serán liberados y podrán rescatar a los demás. ¿Cuál es el plan para lograr el objetivo?
Los prisioneros se emparejan. En una pareja (A, B) de prisioneros A dice el color que ve en la cabeza de B, quien dice el color opuesto que ve en la cabeza de A. Entonces, si ambos usan sombreros del mismo color, A es liberado (y B no), si los colores son diferentes, B se libera (y A no). En total, 5 presos responden correctamente y 5 no. Esto supone que la pareja puede comunicar quién es A y quién es B, lo cual puede no estar permitido.
Alternativamente, los prisioneros forman dos grupos de 5. Un grupo supone que el número de sombreros rojos es par, el otro supone que hay un número impar de sombreros rojos. Al igual que en la variante con oído, a partir de esta suposición pueden deducir el color de su sombrero. Exactamente un grupo acertará, por lo que 5 presos responden correctamente y 5 no.
Tenga en cuenta que los prisioneros no pueden encontrar una estrategia que garantice la liberación de más de 5 prisioneros. De hecho, para un solo prisionero, hay tantas distribuciones de colores de sombrero cuando dice la respuesta correcta como cuando no la dice. Por lo tanto, hay tantas distribuciones de colores de sombreros donde 6 o más prisioneros dicen la respuesta correcta que cuando 4 o menos lo hacen.
En esta variante, un número contablemente infinito de prisioneros, cada uno con un sombrero rojo o azul desconocido y asignado al azar, se alinean en una sola fila. Cada prisionero mira en dirección opuesta al comienzo de la fila, y cada prisionero puede ver todos los sombreros frente a él y ninguno de los sombreros detrás. Comenzando desde el principio de la fila, cada prisionero debe identificar correctamente el color de su sombrero o será asesinado en el acto. Como antes, los prisioneros tienen la oportunidad de reunirse de antemano, pero a diferencia de antes, una vez en la fila, ningún prisionero puede escuchar lo que dicen los demás prisioneros. La pregunta es: ¿hay alguna forma de garantizar que sólo se mate a un número finito de prisioneros?
Si se acepta el axioma de elección y se supone que cada uno de los prisioneros tiene la capacidad (poco realista) de memorizar una cantidad incontablemente infinita de información y realizar cálculos con una complejidad computacional incontablemente infinita , la respuesta es sí. De hecho, incluso si permitimos un número incontable de colores diferentes para los sombreros y un número incontable de prisioneros, el axioma de elección proporciona una solución que garantiza que sólo un número finito de prisioneros deben morir, siempre que cada prisionero pueda ver los sombreros de los demás. prisionero (no sólo los que están delante de ellos en la fila), o al menos que cada prisionero pueda ver todos los demás sombreros excepto un número finito. La solución para el caso de dos colores es la siguiente, y la solución para el caso de colores infinitos e incontables es esencialmente la misma:
Los prisioneros que hacen fila forman una secuencia de 0 y 1, donde 0 representa el azul y 1 representa el rojo. Antes de ser colocados en la fila, los prisioneros definen la siguiente relación de equivalencia sobre todas las secuencias posibles en las que podrían ser colocados: Dos secuencias son equivalentes si son idénticas después de un número finito de entradas. A partir de esta relación de equivalencia, los prisioneros obtienen una colección de clases de equivalencia. Suponiendo el axioma de elección, existe un conjunto de secuencias representativas, una de cada clase de equivalencia. ( Casi todos los valores específicos son imposibles de calcular, pero el axioma de elección implica que existe algún conjunto de valores, por lo que suponemos que los prisioneros tienen acceso a un oráculo ).
Cuando se los coloca en su fila, cada prisionero puede ver todos menos un número finito de sombreros y, por lo tanto, puede ver a qué clase de equivalencia pertenece la secuencia real de sombreros. (Esto supone que cada prisionero puede realizar un número incontablemente infinito de comparaciones para encontrar una coincidencia, y cada comparación de clase requiere un número contablemente infinito de comparaciones individuales de sombreros). Luego proceden a adivinar el color de su sombrero como si estuvieran en la secuencia representativa de la clase de equivalencia apropiada. Debido a que la secuencia real y la secuencia representativa están en la misma clase de equivalencia, sus entradas son las mismas después de un número finito N de prisioneros. Todos los prisioneros después de estos primeros N prisioneros se salvan.
Debido a que los prisioneros no tienen información sobre el color de su propio sombrero y harían la misma suposición sin importar el color que tenga, cada prisionero tiene un 50% de posibilidades de ser asesinado. Puede parecer paradójico que un número infinito de prisioneros tenga la misma probabilidad de ser asesinado y, sin embargo, es seguro que sólo un número finito muere. La solución a esta paradoja radica en el hecho de que la función empleada para determinar la conjetura de cada prisionero no es una función medible .
Para ver esto, consideremos el caso de ningún prisionero asesinado. Esto sucede si y sólo si la secuencia real es una de las secuencias representativas seleccionadas. Si las secuencias de 0 y 1 se ven como representaciones binarias de un número real entre 0 y 1, las secuencias representativas forman un conjunto no mensurable . (Este conjunto es similar a un conjunto de Vitali , la única diferencia es que las clases de equivalencia se forman con respecto a números con representaciones binarias finitas en lugar de todos los números racionales). Por lo tanto, no se puede asignar ninguna probabilidad al caso de que se mate a cero prisioneros. El argumento es similar para otros números finitos de prisioneros asesinados, correspondientes a un número finito de variaciones de cada representante.
Esta variante es la misma que la anterior excepto que los prisioneros pueden escuchar los colores que gritan otros prisioneros. La pregunta es, ¿cuál es la estrategia óptima para los prisioneros de modo que muera la menor cantidad en el peor de los casos?
Resulta que, si se permite a los prisioneros escuchar los colores gritados por los demás prisioneros, es posible garantizar la vida de todos los prisioneros excepto el primero, que muere con un 50% de probabilidad.
Para hacer esto, definimos la misma relación de equivalencia que arriba y nuevamente seleccionamos una secuencia representativa de cada clase de equivalencia. Ahora, etiquetamos cada secuencia en cada clase con un 0 o un 1. Primero, etiquetamos la secuencia representativa con un 0. Luego, etiquetamos cualquier secuencia que difiera de la secuencia representativa en un número par de lugares con un 0. y cualquier secuencia que difiera de la secuencia representativa en un número impar de lugares con un 1. De esta manera, hemos etiquetado cada secuencia infinita posible con un 0 o un 1 con la importante propiedad de que dos secuencias cualesquiera que difieran solo en un dígito tienen etiquetas opuestas.
Ahora, cuando el director le pide a la primera persona que diga un color, o en nuestra nueva interpretación, un 0 o un 1, simplemente dice en voz alta la etiqueta de la secuencia que ve. Con esta información, todos los que le siguen pueden determinar exactamente cuál es su propio color de sombrero. La segunda persona ve todo menos el primer dígito de la secuencia que ve la primera persona. Por lo tanto, hasta donde él sabe, hay dos secuencias posibles que la primera persona podría haber etiquetado: una que comienza con un 0 y otra que comienza con un 1. Debido a nuestro esquema de etiquetado, estas dos secuencias recibirían etiquetas opuestas, por lo que, según nuestro esquema de etiquetado, estas dos secuencias recibirían etiquetas opuestas, por lo que En base a lo que dice la primera persona, la segunda persona puede determinar cuál de las dos posibles cuerdas vio la primera persona y, por lo tanto, puede determinar su propio color de sombrero. De manera similar, cada persona posterior en la fila conoce cada dígito de la secuencia excepto el correspondiente a su propio color de sombrero. Él conoce a los que están delante de él porque fueron llamados, y a los que están detrás de él porque puede verlos. Con esta información, puede utilizar la etiqueta mencionada por la primera persona para determinar el color de su propio sombrero. Por lo tanto, todos, excepto la primera persona, siempre adivinan correctamente.
La versión de Ebert del problema establece que todos los jugadores que adivinan deben hacerlo al mismo tiempo predeterminado, pero que no todos los jugadores están obligados a adivinar. Ahora no todos los jugadores pueden adivinar correctamente, por lo que los jugadores ganan si al menos un jugador adivina y todos los que adivinan lo hacen correctamente. ¿Cómo pueden los jugadores maximizar sus posibilidades de ganar?
Una estrategia para resolver esta versión del problema del sombrero emplea códigos Hamming , que se utilizan comúnmente para detectar y corregir errores en la transmisión de datos . La probabilidad de ganar será mucho mayor que el 50%, dependiendo del número de jugadores en la configuración del rompecabezas: por ejemplo, una probabilidad de ganar del 87,5% para 7 jugadores.
Se pueden aplicar estrategias similares a equipos de tamaño N = 2 k −1 y lograr una tasa de victorias (2 k -1)/2 k . Por lo tanto , la estrategia del código Hamming produce mayores tasas de ganancia para valores mayores de N.
En esta versión del problema, cualquier suposición individual tiene un 50% de posibilidades de ser correcta. Sin embargo, el enfoque del código Hamming funciona concentrando conjeturas erróneas en determinadas distribuciones de sombreros. En algunos casos, todos los jugadores adivinarán incorrectamente; mientras que en los demás casos, sólo un jugador adivinará, pero correctamente. Si bien la mitad de todas las conjeturas siguen siendo incorrectas, esto da como resultado que los jugadores ganen más del 50% de las veces.
Un ejemplo sencillo de este tipo de solución con tres jugadores resulta instructivo. Con tres jugadores, hay ocho posibilidades; en dos de ellos todos los jugadores tienen el mismo color de sombrero, y en los otros seis, dos jugadores tienen un color y el otro tiene el otro color.
Los jugadores pueden garantizar que ganarán en los últimos casos (75% de las veces) con la siguiente estrategia:
En los dos casos en que los tres jugadores tengan el mismo color de sombrero, todos adivinarán incorrectamente. Pero en los otros seis casos, sólo un jugador adivinará, y correctamente, que su sombrero es opuesto al de sus compañeros. [22]
sombrero rompecabezas todd.
