Rompecabezas de inducción

A un grupo de niños atentos se les dice que algunos tienen la cara embarrada. Cada niño puede ver las caras de los demás, pero no puede saber si la suya está embarrada. Se les dice que los que tengan la cara embarrada deben dar un paso al frente, pero cualquier niño con la cara limpia que dé un paso al frente será castigado. A la cuenta de tres, cada niño que crea que tiene la cara embarrada debe dar un paso al frente simultáneamente; cualquier niño que le haga una señal a otro de cualquier manera será castigado. Si algún niño con la cara embarrada no ha dado un paso al frente, el proceso se repetirá. En una iteración dada, todos los niños embarrados, y solo ellos, dan un paso al frente. ¿Cuál es su proceso de pensamiento y en qué turno ocurre? ^{[ 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 (${\displaystyle X}$) darán un paso al frente juntos por turno${\displaystyle X}$Los niños tienen información diferente, dependiendo de si su propia cara está embarrada o no. Cada miembro de${\displaystyle X}$ve${\displaystyle X-1}$caras embarradas, y sabe que esos niños darán un paso al frente a su vez.${\displaystyle X-1}$si son las únicas caras embarradas. Cuando eso no ocurre, cada miembro de${\displaystyle X}$sabe que él o ella también es miembro de${\displaystyle X}$y da un paso adelante por turno${\displaystyle X}$. Cada no miembro de${\displaystyle X}$ve${\displaystyle X}$caras embarradas, y no esperará que nadie dé un paso al frente hasta que al menos se dé la vuelta.${\displaystyle X}$.

Supongamos que hay dos niños, Alice y Bob , y que solo Alice está embarrada (${\displaystyle X=1}$). 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 al frente en el primer turno. Bob, al ver la cara embarrada de Alice, no tiene forma de saber en el primer turno si su propia cara está embarrada o no, por lo que no da un paso al frente por miedo al castigo (solo después de que Alice haya dado un paso al frente y el juego haya terminado, Bob entiende que su cara debe estar limpia). Si tanto Alice como Bob están sucios (${\displaystyle X=2}$), cada uno está en la posición de Bob cuando${\displaystyle X=1}$Ninguno de los dos se atreve a dar un paso al frente en el primer turno. Sin embargo, en el segundo turno, Bob sabe que Alice debe haber visto que tiene la cara embarrada (porque ella no dio un paso al frente en el primer turno), así que da un paso al frente en el segundo turno. Siguiendo la misma lógica, Alice también da un paso al frente en el segundo turno.

Supongamos que hay un tercer hijo, Charlie. Si solo Alice está embarrada (${\displaystyle X=1}$), no verá caras embarradas y dará un paso adelante en la primera curva. Si tanto Alice como Bob están embarrados (${\displaystyle X=2}$), ninguno puede dar un paso al frente en el primer turno, pero cada uno sabrá en el segundo turno 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 darán un paso al frente en el segundo turno. Charlie, al ver dos caras embarradas, no sabe en el segundo turno si su propia cara está embarrada o no hasta que Alice y Bob den un paso al frente (lo que indica que su propia cara está limpia). Si los tres están embarrados (${\displaystyle X=3}$), cada uno está en la posición de Charlie cuando${\displaystyle X=2}$: cuando dos personas no dan un paso al frente en el segundo turno, cada una sabe que la otra ve dos caras embarradas, lo que significa que su propia cara debe estar embarrada, y cada una da un paso al frente en el tercer turno.

Se puede demostrar que${\displaystyle X}$Los niños embarrados darán un paso al frente en el turno${\displaystyle X}$. ^{[ 4 ] [ 14 ]}

Representación del rompecabezas "Niños Embarrados" para dos jugadores en forma extensiva . El movimiento preliminar, por naturaleza , está coloreado de verde. Alice está coloreada de rojo y Bob de azul. Este juego tiene un único equilibrio de Nash . Las acciones predichas por este equilibrio están coloreadas de negro.

El rompecabezas de los niños embarrados también se puede resolver mediante inducción hacia atrás de la teoría de juegos . ^{[ 13 ]} El rompecabezas de los niños embarrados se puede representar como un juego de forma extensiva de información imperfecta . Cada jugador tiene dos acciones: quedarse atrás y avanzar. Hay un movimiento predeterminado al comienzo del juego, que determina qué niños tendrán la cara embarrada y cuáles no. Los niños no se comunican como en los juegos no cooperativos . Cada movimiento es simultáneo de los niños. Es un juego secuencial de duración ilimitada. La solución basada en la teoría de juegos requiere algunas suposiciones adicionales:

1. Todos los niños son racionales y la racionalidad de todos los niños es de conocimiento común . Esto significa que Alicia es racional, Alicia sabe que Bob es racional y Alicia sabe que Bob sabe que Charlie es racional, y así sucesivamente.
2. Dar un paso al frente sin tener la cara sucia conlleva una gran penalización.
3. Dar un paso al frente con la cara sucia tiene su recompensa.
4. Cada golpe conlleva una penalización menor, también conocida como factor de descuento, para cada niño hasta que alguno de ellos dé un paso al frente. Cualquier múltiplo de la penalización menor siempre es un mal menor que la penalización mayor.

Si solo Alice está embarrada, la última suposición hace que sea irracional que dude. Si Alice y Bob están embarrados, Alice sabe que la única razón por la que Bob se queda atrás después del primer golpe es el temor a recibir la gran penalización de avanzar sin la cara embarrada. En el caso de${\displaystyle X}$niños embarrados, recibiendo${\displaystyle X}$veces la penalización menor sigue siendo mejor que la penalización mayor.

El rey llamó a los tres hombres más sabios del país a su corte para decidir quién sería su nuevo consejero. Les colocó un sombrero a cada uno, de manera que cada sabio pudiera ver los sombreros de los demás, pero ninguno podía ver el suyo. Cada sombrero era blanco o azul. El rey les prometió a los sabios que al menos uno de ellos llevaría un sombrero azul; es decir, podía haber uno, dos o tres sombreros azules, pero no ninguno. El rey también anunció que el concurso sería justo para los tres. Además, los sabios tenían prohibido hablar entre sí. El rey declaró que el primero que se pusiera de pie y anunciara correctamente el color de su propio sombrero se convertiría en su nuevo consejero. Los sabios permanecieron sentados durante mucho tiempo antes de que uno se levantara y anunciara correctamente la respuesta. ¿Qué dijo y cómo lo averiguó? ^{[ 15 ]}

El acertijo de los Reyes Magos es uno de los rompecabezas de inducción más sencillos y uno de los indicadores más claros del método utilizado.

• Supongamos que hay un sombrero azul. La persona que lo lleva vería dos sombreros blancos, y como el rey especificó que debe haber al menos un sombrero azul, ese sabio sabría inmediatamente el color de su sombrero. Sin embargo, los otros dos verían un sombrero azul y uno blanco, y no podrían deducir nada de inmediato a partir de sus observaciones. Por lo tanto, este escenario violaría la condición del rey de que la competencia fuera justa para todos. Así pues, debe haber al menos dos sombreros azules.
• Supongamos entonces que hubiera dos sombreros azules. Cada sabio con un sombrero azul vería un sombrero azul y uno blanco. Suponiendo que ya se hubieran dado cuenta de que no puede haber solo uno (usando el escenario anterior), sabrían que debe haber al menos dos sombreros azules y, por lo tanto, sabrían inmediatamente que cada uno llevaba un sombrero azul. Sin embargo, el hombre con el sombrero blanco vería dos sombreros azules y no podría inferir inmediatamente ninguna información a partir de sus observaciones. Este escenario, entonces, también violaría la especificación de que el concurso sería justo para todos. Por lo tanto, debe haber tres sombreros azules.

Dado que debe haber tres sombreros azules, el primero que lo averigüe se pondrá de pie y dirá azul.

Solución alternativa: Esto no requiere la regla de que el concurso sea justo para todos. Más bien, se basa en el hecho de que todos son sabios y que les lleva algún tiempo llegar a una solución. Solo puede haber tres escenarios: un sombrero azul, dos sombreros azules o tres sombreros azules. Si solo hubiera un sombrero azul, quien lo llevara vería dos sombreros blancos y sabría rápidamente que tiene que tener un sombrero azul, así que se levantaría y lo anunciaría de inmediato. Como esto no ha sucedido, entonces debe haber al menos dos sombreros azules. Si hubiera dos sombreros azules, cualquiera de los que llevaran un sombrero azul miraría al otro lado y vería un sombrero azul y uno 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 vería 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, la primera persona que usó el sombrero azul sabría que lo llevaba puesto y podría levantarse y anunciarlo. Como es muy fácil deducir que uno o dos sombreros azules son suficientes, y nadie se ha levantado rápidamente, entonces todos deben estar usando sombreros azules.

En el reino de Josefina, toda mujer debía aprobar un examen de lógica antes de poder casarse. ^{[ 16 ]} Toda mujer casada conocía la fidelidad de todos los hombres del reino, excepto la de su propio marido, y la etiqueta exigía que ninguna mujer supiera de la fidelidad de su esposo. Además, un disparo en cualquier casa del reino se oiría en cualquier otra. La reina Josefina anunció que se había descubierto al menos un hombre infiel en el reino, y que toda mujer que supiera que su marido le era infiel debía dispararle a medianoche del día siguiente al descubrimiento de su infidelidad. ¿Cómo se las arreglaban las esposas con esto?

El problema de Josefina es otro buen ejemplo de un caso general.

• Si solo hay un marido infiel, todas las mujeres del reino lo saben, excepto su esposa, quien cree que todos son fieles. Por lo tanto, en cuanto la reina le cuenta que existen hombres infieles, sabe que su marido debe serlo y lo mata.
• Si hay dos maridos infieles, ambas esposas creen que solo hay uno (el otro). Por lo tanto, esperarán que se cumpla el caso anterior y que la esposa del otro marido le dispare a medianoche del día siguiente. Al no oír ningún disparo, se darán cuenta de que el caso anterior no se cumple , por lo que debe haber más de un marido infiel y (como saben que todos los demás son fieles) el otro debe ser su propio marido.
• Si hay tres maridos infieles, cada una de sus esposas cree que solo hay dos, por lo que esperarán que se dé el caso anterior y que ambos maridos sean asesinados a tiros al segundo día. Al no oír ningún disparo, se darán cuenta de que el caso anterior no se cumple, por lo que debe haber más de dos maridos infieles y, como antes, su propio marido es el único candidato a ser el infiel.
• En general, si hay n maridos infieles, cada una de sus esposas creerá que hay n-1 y esperará oír un disparo a medianoche del día n-1 . Cuando no lo oyen, saben que su propio marido fue el n - ésimo.

Este problema también se conoce como el problema de los maridos infieles, el problema de las esposas infieles o el problema de los niños embarrados. 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 libro de texto clásico de CL Liu, 'Elementos de Matemáticas Discretas'. ^{[ 17 ]}

En la Convención Secreta de Lógicos, el Maestro Lógico colocó una banda en la cabeza de cada asistente, de manera que todos los demás pudieran verla, pero la persona en cuestión no. Había bandas de muchos colores diferentes. Los Lógicos se sentaron en círculo, y el Maestro les indicó que se debía tocar una campana en el bosque a intervalos regulares: en el momento en que un Lógico supiera el color de su propia banda en la frente, debía marcharse al sonar la siguiente campana. Se les ordenó no hablar, ni usar un espejo, una cámara ni ningún otro método para evitar 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 se marchara a tiempo sería expulsado bruscamente en el momento correcto. Del mismo modo, cualquiera que intentara marcharse antes de tiempo sería retenido bruscamente y expulsado en el momento correcto. El Maestro tranquilizó al grupo afirmando que el enigma no sería imposible para ningún Verdadero Lógico presente. ¿Cómo lo hicieron? ^{[ 18 ]}

La situación de Alicia en la convención de lógicos es inducción general más un salto lógico.

• Un salto lógico: Cada color debe aparecer al menos dos veces alrededor del círculo. Esto se debe a que el Maestro afirmó que no sería imposible para ningún lógico resolver el acertijo. Si algún color apareciera solo una vez alrededor del círculo, el lógico que lo tuviera no tendría forma de saber que ese color existe en el problema, y ​​le sería imposible responder.
• Cada uno de los Lógicos puede mirar alrededor del círculo y contar cuántas veces ve cada color. Supongamos que eres uno de los Lógicos y ves otro color solo una vez. Dado que sabes que cada color debe aparecer al menos dos veces alrededor del círculo, la única explicación para un color que aparece solo una vez es que sea el color de tu propia banda. Por la misma razón, solo puede haber un color así, y por lo tanto te irías al sonar la primera campana.
• Asimismo, cualquier lógico que vea otro color solo una vez debería poder determinar el suyo propio y marcharse con dignidad o ser expulsado como infiltrado. De igual modo, cualquier color del que solo haya dos bandas será eliminado tras la primera campanada. A partir de entonces, deberá haber al menos tres bandas de cualquier color restante.
• Supongamos que no ves ningún color una vez, pero sí ves un color dos veces. Si estas fueran las únicas bandas de ese color, entonces estos dos lógicos deberían haberse marchado al sonar la primera campana. Como no lo hicieron, solo puede deberse a que tu propia banda es del mismo color, por lo que puedes marcharte al sonar la segunda campana.
• Por lo tanto, cada lógico observaba hasta que un grupo de un color determinado, que esperaban que se marchara, no lo hacía. Entonces sabrían que tenían ese color y se marcharían al sonar la siguiente campana.
• Cuando solo quedaba un color, ese color se iría con la siguiente campana, porque sabrían que no podrían tener ningún otro color (ya que entonces les sería imposible saber cuál es su color).

Varios jugadores llevan cada uno un sombrero, que puede ser de varios colores específicos. Los jugadores pueden ver los colores de los sombreros de al menos algunos de los demás jugadores, pero no el suyo propio. Con una comunicación muy restringida o nula, algunos jugadores deben adivinar el color de su sombrero. El problema consiste en encontrar una estrategia para que los jugadores determinen el color de sus sombreros basándose en los sombreros que ven y en lo que hacen los demás jugadores. En algunas versiones, compiten por ser los primeros en adivinar correctamente; en otras, pueden elaborar una estrategia de antemano para cooperar y maximizar la probabilidad de acertar. ^{[ 19 ]}

Una variante recibió cierta publicidad como resultado de la tesis doctoral de Todd Ebert de 1998 en la Universidad de California, Santa Bárbara . ^{[ 20 ]} Es una cuestión de estrategia sobre un juego cooperativo , que tiene conexiones con la teoría de la codificación algebraica . ^{[ 21 ]}

Tres jugadores reciben un sombrero rojo o uno azul. Deben levantar la mano si ven a otro jugador con un sombrero rojo, mientras están de pie en círculo mirándose unos a otros. Gana quien adivine primero el color de su sombrero.

Los tres jugadores levantan la mano. Tras unos minutos de verse sin adivinar, uno anuncia "Rojo" y gana. ¿Cómo lo consiguió el ganador y de qué color son los sombreros de todos?

Primero, si dos personas tuvieran sombreros azules, no todos habrían levantado la mano. Luego, 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. Por lo tanto, cualquier jugador que vea un sombrero azul puede adivinar al instante. Finalmente, el ganador se da cuenta de que, como nadie adivina al mismo tiempo, no debe haber sombreros azules, por lo que todos los sombreros deben ser rojos. ^{[ 22 ]}

En el caso de que cada jugador tenga que adivinar, pero sea libre de elegir cuándo hacerlo, existe una estrategia cooperativa que permite que todos los jugadores acierten a menos que todos los sombreros sean del mismo color. Cada jugador debe actuar de la siguiente manera:

1. Cuenta la cantidad de sombreros azules (b) y sombreros rojos (r) que veas.
2. Espera b segundos o r segundos, lo que ocurra primero.
3. Si nadie ha hablado todavía, adivina que tu sombrero es azul si ves menos sombreros azules que rojos, o rojo si ves menos sombreros rojos que azules.
4. Si aún no has hablado, adivina que tu sombrero es del color opuesto al de una de las primeras personas que habló.

Supongamos que en total hay B sombreros azules y R sombreros rojos. Hay tres casos.

Si B = R, entonces los jugadores que llevan sombreros azules ven B  −  1 sombreros azules y B sombreros rojos, así que esperan B  −  1 segundos y adivinan correctamente que llevan un sombrero azul. De manera similar, los jugadores que llevan un sombrero rojo esperarán R  −  1 segundos antes de adivinar correctamente que llevan un sombrero rojo. Por lo tanto, todos los jugadores aciertan al mismo tiempo.

Si B < R , quienes lleven un sombrero azul verán B  −  1 sombreros azules y R sombreros rojos, mientras que quienes lleven un sombrero rojo verán B sombreros azules y R  −  1 sombreros rojos. Dado que B  −  1 < B ≤ R − 1, los jugadores que lleven un sombrero azul serán los primeros en hablar, adivinando correctamente que su sombrero es azul. Los demás jugadores adivinarán entonces correctamente que su sombrero es rojo.    

El caso en el que R  < B es similar. 

En esta variante hay 3 prisioneros y 3 sombreros. A cada prisionero se le asigna un sombrero al azar, rojo o azul. Cada persona puede ver los sombreros de otros dos, pero no el suyo. A una señal, cada uno debe adivinar el color de su propio sombrero o pasar. Ganan la libertad si al menos una persona acierta y ninguna se equivoca (pasar no es ni correcto ni incorrecto).

Este rompecabezas no tiene una estrategia ganadora al 100%, pero se puede ganar con un 75% de probabilidad. 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 de Hamming . ^{[ 23 ]}

Cuatro prisioneros son arrestados por un crimen , pero el juez les ofrece eximirlos del castigo si pueden resolver un acertijo lógico. ^{[ 24 ]}

Tres de los hombres se colocan en fila. A mira hacia la pared, B hacia A, y C hacia B y A. Un cuarto hombre se sitúa detrás de una pared. Los cuatro llevan sombreros: dos negros y dos blancos. Cada prisionero lleva uno de ellos y solo puede ver los sombreros que tiene delante, ni los que lleva puestos ni los que tiene detrás. El cuarto hombre, detrás de la pantalla, no puede ver ni ser visto por ningún otro prisionero. No se permite la comunicación entre los prisioneros. Si algún prisionero logra identificar con total certeza el color de su sombrero (sin adivinar), debe anunciarlo y los cuatro prisioneros quedan libres.

Los prisioneros saben que solo hay dos sombreros de cada color. Por lo tanto, si C observa que A y B tienen sombreros del mismo color, deducirá que su propio sombrero es del color opuesto. Sin embargo, si A y B tienen sombreros de colores diferentes, C no puede decir nada. La clave está en que el prisionero B, tras un intervalo adecuado y sabiendo lo que haría C, puede deducir que si C no dice nada, los sombreros de A y B deben ser diferentes; al poder ver el sombrero de A, puede deducir el color de su propio sombrero.

Tras resolver este enigma, se puede obtener cierta comprensión de la naturaleza de la comunicación reflexionando sobre si el significativo silencio del prisionero C viola la regla de "No comunicación" (dado que la comunicación se define habitualmente como la "transferencia de información").

En otra variante, solo participan tres prisioneros y cinco sombreros de colores conocidos (en este ejemplo, dos negros y tres blancos). Los tres prisioneros deben colocarse en línea recta mirando al frente, con A delante y C detrás. Se les informa que habrá dos sombreros negros y tres blancos. A continuación, se coloca un sombrero en la cabeza de cada prisionero; cada uno solo puede ver los sombreros de las personas que tiene delante, no el suyo propio. El primer prisionero que logre adivinar correctamente el color de su sombrero será liberado. No se permite la comunicación entre los prisioneros.

Supongamos que A lleva un sombrero negro:

• Si B también lleva un sombrero negro, C puede darse cuenta inmediatamente de que lleva un sombrero blanco tras mirar los dos sombreros negros que tiene delante.
• Si B lleva un sombrero blanco, C no podrá distinguir el color del suyo (ya que existen uno negro y uno blanco). Por lo tanto, B puede deducir rápidamente, a partir del sombrero negro de A y la falta de respuesta de C, que él (B) lleva un sombrero blanco.

Así que si A lleva un sombrero negro, habrá una respuesta bastante rápida por parte de B o C.

Supongamos que A lleva un sombrero blanco:

• C no ve dos sombreros negros, por lo que no puede determinar el color de su sombrero.
• B solo ve un sombrero blanco, así que no puede decir nada sobre su sombrero.

En este caso, A, B y C permanecerían en silencio durante algún tiempo, hasta que A finalmente dedujera que debe tener un sombrero blanco porque C y B han permanecido en silencio durante algún tiempo.

Como ya se mencionó, hay tres sombreros blancos y dos negros en total, y los tres prisioneros lo saben. En este acertijo, se puede suponer que los tres prisioneros son muy listos e inteligentes. Si C no pudo adivinar el color de su propio sombrero, es porque vio dos sombreros blancos o uno de cada color. Si vio dos sombreros negros, pudo 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, rojo o azul, pero desconocen la cantidad de sombreros de cada color. Los prisioneros se alinearán en fila india, de manera que cada uno pueda ver los sombreros que tiene delante, pero no los que tiene detrás. Comenzando por el prisionero que está al final de la fila y avanzando hacia adelante, cada uno, por turno, debe decir una sola palabra que debe ser "rojo" o "azul". Si la palabra coincide con el color de su sombrero, son liberados; de lo contrario, son ejecutados en el acto. Un guardia comprensivo les advierte de esta prueba una hora antes y les dice que pueden formular un plan para que, siguiendo las reglas establecidas, 9 de los 10 prisioneros sobrevivan con seguridad y 1 tenga un 50% de probabilidades de sobrevivir. ¿Cuál es el plan para lograr el objetivo?

Los prisioneros acuerdan que si el primero ve un número impar de sombreros rojos, dirá "rojo". De esta forma, los otros nueve prisioneros sabrán el color de su propio sombrero después de que el prisionero que esté detrás de ellos responda.

Como antes, hay 10 prisioneros y 10 sombreros. A cada prisionero se le asigna un sombrero al azar, rojo o azul, pero desconocen la cantidad de sombreros de cada color. Los prisioneros están distribuidos en la sala de manera que puedan ver los sombreros de los demás, pero no el suyo. 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 guardia comprensivo les advierte de esta prueba una hora antes. Si logran formular un plan siguiendo las reglas establecidas, 5 de los 10 prisioneros 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 cada pareja (A, B), A dice el color que ve en la cabeza de B, quien dice el color opuesto que ve en la cabeza de A. Si ambos llevan sombreros del mismo color, A queda libre (y B no); si los colores son diferentes, B queda libre (y A no). En total, 5 prisioneros responden correctamente y 5 no. Esto supone que la pareja puede comunicarse para saber quién es A y quién es B, lo cual podría no estar permitido.

Como alternativa, los prisioneros forman dos grupos de 5. Un grupo supone que el número de sombreros rojos es par, el otro supone que es impar. Al igual que en la variante con audición, pueden deducir el color de su sombrero a partir de esta suposición. Exactamente un grupo acertará, por lo que 5 prisioneros responderán correctamente y 5 no.

Cabe destacar 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, existen tantas distribuciones de colores de sombreros en las que da la respuesta correcta como en las que no la da. Por lo tanto, existen tantas distribuciones de colores de sombreros en las que 6 o más prisioneros dan la respuesta correcta como en las que 4 o menos lo hacen.

En esta variante, un número infinito numerable de prisioneros, cada uno con un sombrero rojo o azul desconocido y asignado al azar, se alinean en fila india. Cada prisionero da la espalda al inicio de la fila y puede ver todos los sombreros que tiene delante, pero ninguno de los que tiene detrás. Comenzando desde el principio, cada prisionero debe identificar correctamente el color de su sombrero o será ejecutado en el acto. Como antes, los prisioneros tienen la oportunidad de conocerse previamente, pero a diferencia de antes, una vez en la fila, ningún prisionero puede oír lo que dicen los demás. La pregunta es: ¿hay alguna manera de asegurar que solo un número finito de prisioneros sean ejecutados?

Si se acepta el axioma de elección y se supone que cada prisionero tiene la capacidad (irreal) de memorizar una cantidad infinita no numerable de información y realizar cálculos con una complejidad computacional infinita no numerable , la respuesta es sí. De hecho, incluso si permitimos un número no numerable de colores diferentes para los sombreros y un número no numerable de prisioneros, el axioma de elección proporciona una solución que garantiza que solo un número finito de prisioneros deben morir siempre que cada prisionero pueda ver los sombreros de todos los demás prisioneros (no solo los que están delante de él en una fila), o al menos que cada prisionero pueda ver todos los sombreros excepto un número finito de los demás. La solución para el caso de dos colores es la siguiente, y la solución para el caso de un número infinito no numerable de colores es esencialmente la misma:

Los prisioneros que hacen fila forman una secuencia de 0 y 1, donde 0 representa el azul y 1 el rojo. Antes de ser colocados en la fila, definen la siguiente relación de equivalencia sobre todas las secuencias posibles: 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, obtienen un conjunto 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 les coloca en fila, cada prisionero puede ver todos los sombreros excepto un número finito, 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 infinito no numerable de comparaciones para encontrar una coincidencia, y que cada comparación de clases requiere un número infinito numerable 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. Dado 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 son salvados.

Dado que los prisioneros desconocen el color de su propio sombrero y adivinarían el color independientemente del que tenga, cada prisionero tiene un 50 % de probabilidades de morir. Puede parecer paradójico que un número infinito de prisioneros tenga la misma probabilidad de morir, cuando en realidad solo muere un número finito. La solución a esta paradoja reside en que la función empleada para determinar la suposición de cada prisionero no es una función medible .

Para ver esto, consideremos el caso de que no muera ningún prisionero. Esto sucede si y solo si la secuencia real es una de las secuencias representativas seleccionadas. Si las secuencias de 0 y 1 se consideran 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 , con la única diferencia de 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 evento de que muera ningún prisionero. El argumento es similar para otros números finitos de prisioneros asesinados, que corresponden a un número finito de variaciones de cada representante.

Esta variante es igual a la anterior, salvo que los prisioneros pueden oír los colores que anuncian otros prisioneros. La pregunta es: ¿cuál es la estrategia óptima para que, en el peor de los casos, muera el menor número de prisioneros?

Resulta que, si se permite a los prisioneros oír los colores que anuncian los demás, es posible garantizar la vida de todos excepto del primero, que muere con un 50% de probabilidad.

Para ello, definimos la misma relación de equivalencia que antes y seleccionamos una secuencia representativa de cada clase de equivalencia. Ahora, etiquetamos cada secuencia de cada clase con un 0 o un 1. Primero, etiquetamos la secuencia representativa con un 0. Luego, etiquetamos con un 0 cualquier secuencia que difiera de la representativa en un número par de posiciones, y con un 1 cualquier secuencia que difiera de la representativa en un número impar de posiciones. De esta manera, hemos etiquetado con un 0 o un 1 cualquier secuencia infinita posible, con la importante propiedad de que dos secuencias cualesquiera que difieran en un solo dígito tienen etiquetas opuestas.

Ahora, cuando el vigilante le pide a la primera persona que diga un color, o en nuestra nueva interpretación, un 0 o un 1, simplemente dice la etiqueta de la secuencia que ve. Con esta información, todos los que están después pueden determinar exactamente cuál es el color de su propio sombrero. La segunda persona ve todos los dígitos de la secuencia que ve la primera persona, excepto el primero. Por lo tanto, hasta donde sabe, hay dos secuencias posibles que la primera persona podría haber estado etiquetando: una que comienza con un 0 y otra que comienza con un 1. Debido a nuestro sistema de etiquetado, estas dos secuencias recibirían etiquetas opuestas, así que, basándose en lo que dice la primera persona, la segunda persona puede determinar cuál de las dos posibles cadenas vio la primera persona y, por lo tanto, puede determinar el color de su propio sombrero. De manera similar, cada persona posterior en la fila conoce todos los dígitos de la secuencia excepto el que corresponde al color de su propio sombrero. Conoce a los que están antes que él porque fueron mencionados y a los que están después porque puede verlos. Con esta información, puede usar 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 del problema de Ebert establece que todos los jugadores que adivinan deben hacerlo al mismo tiempo predeterminado, pero no es obligatorio que todos adivinen. Ahora bien, no todos los jugadores pueden adivinar correctamente, por lo que los jugadores ganan si al menos uno 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 de Hamming , que se utilizan habitualmente 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 tamaños de equipo de N = 2 ^k −1 y lograr una tasa de victorias de (2 ^k -1)/2 ^k . Por lo tanto, la estrategia del código de Hamming produce mayores tasas de victorias para valores más grandes de N .

En esta versión del problema, cada intento individual tiene un 50 % de probabilidad de ser correcto. Sin embargo, el método del código de Hamming funciona concentrando los intentos erróneos en ciertas distribuciones de sombreros. En algunos casos, todos los jugadores adivinarán incorrectamente; mientras que en otros, solo uno adivinará correctamente. Si bien la mitad de los intentos siguen siendo incorrectos, esto resulta en 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, existen ocho posibilidades: en dos de ellas, todos los jugadores tienen el mismo color de sombrero, y en las otras seis, dos jugadores tienen un color y el otro jugador tiene el otro color.

Los jugadores pueden garantizarse la victoria en estos últimos casos (el 75% de las veces) con la siguiente estrategia:

1. Cualquier jugador que observe dos sombreros de dos colores diferentes permanece en silencio.
2. Cualquier jugador que observe dos sombreros del mismo color adivina el color opuesto.

En los dos casos en que los tres jugadores tienen el mismo color de sombrero, todos adivinarán incorrectamente. Pero en los otros seis casos, solo un jugador adivinará, y correctamente, que su sombrero es del color opuesto al de sus compañeros. ^{[ 25 ]}