Los acertijos de inducción son acertijos lógicos , que son ejemplos de razonamiento multiagente , donde la solución evoluciona junto con el principio de inducción . [1] [2]
En un escenario de rompecabezas siempre participan varios jugadores con la misma capacidad de razonamiento, que pasan por los mismos pasos de razonamiento. Según el principio de inducción, la solución del caso más simple hace obvia la solución del siguiente caso complicado. Una vez que se resuelve el caso más simple del rompecabezas de inducción, se resuelve el rompecabezas completo.
Las características típicas de estos rompecabezas incluyen cualquier rompecabezas en el que cada participante tiene una pieza dada de información (generalmente como conocimiento común ) sobre todos los demás participantes pero no sobre sí mismos. Además, generalmente, se da algún tipo de pista para sugerir que los participantes pueden confiar en la inteligencia de los demás: son capaces de aplicar la teoría de la mente (que "cada participante sabe 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 embarrados es el rompecabezas de inducción que aparece con mayor frecuencia en la literatura científica sobre lógica epistémica . [4] [5] [6] El rompecabezas de los niños embarrados es una variante de los conocidos rompecabezas de los hombres sabios o de las esposas/maridos infieles. [7]
Los rompecabezas del sombrero son variaciones de los rompecabezas de inducción que datan de 1961. [8] En muchas variaciones, los rompecabezas del sombrero se describen en el contexto de prisioneros. [9] [10] En otros casos, los rompecabezas del sombrero se describen en el contexto de hombres sabios. [11] [12]
A un grupo de niños atentos se les dice que algunos de ellos tienen la cara embarrada. Cada niño puede ver la cara de los demás, pero no puede decir si la suya está embarrada. Se les dice a los niños 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, todos los niños que crean que su cara está embarrada deben dar un paso adelante simultáneamente; cualquier niño que haga señales a otro de cualquier manera 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 otros tiene) una lógica perfecta, todos los niños con caras embarradas ( ) darán un paso adelante juntos en el turno . Los niños tienen información diferente, dependiendo de si su propia cara está embarrada o no. Cada miembro de ve caras embarradas y sabe que esos niños darán un paso adelante en su turno si son los únicos caras embarradas. Cuando eso no ocurre, cada miembro de sabe que él o ella también es miembro de , y da un paso adelante en el turno . Cada no miembro de ve caras embarradas y no esperará que nadie dé un paso adelante hasta al menos el turno .
Supongamos que hay dos niños, Alice y Bob, y que solo Alice está sucia ( ). Alice sabe que "algunos" niños tienen la cara sucia pero que la de los demás no la tiene, lo que significa que su propia cara debe estar sucia y da un paso adelante en el primer turno. Bob, al ver la cara sucia de Alice, no tiene forma de saber en el primer turno si su propia cara está sucia 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 primer turno. Sin embargo, en el segundo turno Bob sabe que Alice debe haber visto que su cara está sucia (porque no dio un paso adelante en el primer turno), por lo que da un paso adelante en el segundo turno. Usando la misma lógica, Alice también da un paso adelante en el segundo turno.
Supongamos que hay un tercer niño, Charlie. Si solo 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 cada uno sabrá en el turno dos 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 adelante en el turno dos. Charlie, al ver dos caras embarradas, no sabe en el turno dos si su propia cara está embarrada o no hasta que Alice y Bob den 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 el turno tres.
Se puede demostrar que los niños embarrados darán un paso adelante en el turno . [4] [14]
El rompecabezas de los niños embarrados también se puede resolver utilizando la 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 dar un paso adelante. Hay un movimiento por naturaleza al comienzo del juego, que determina los niños con y sin caras embarradas. 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 algunas suposiciones adicionales:
Si sólo Alice está embarrada, 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 de recibir la gran penalización de dar un paso adelante sin la cara embarrada. En el caso de los niños embarrados, recibir la penalización menor es aún mejor que la penalización grande.
El rey convocó a los tres hombres más sabios del país a su corte para decidir quién sería su nuevo consejero. Puso un sombrero en la cabeza de cada uno de ellos, de modo que cada uno 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 sabios de que al menos uno de ellos llevaría un sombrero azul; en otras palabras, podrí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 hombres. A los sabios 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 propio sombrero sería 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 la calculó? [15]
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 lo descubra se levantará 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 hombres sabios y que lleva algún tiempo antes de que lleguen 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, entonces el portador de ese sombrero vería dos sombreros blancos y sabría rápidamente que tiene que tener un sombrero azul, por lo que se pondría de pie y lo anunciaría 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 usan 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 supusiera 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 usaba un sombrero azul. Por lo tanto, como esto no ha sucedido, el primer usuario del sombrero azul sabría que llevaba un sombrero azul y podría ponerse de pie y anunciarlo. Como es tan fácil resolver uno o dos sombreros azules y nadie se ha levantado rápidamente, entonces todos deben llevar sombreros azules.
En el Reino de Josefina, cada mujer tiene que pasar un examen de lógica antes de que se le permita casarse. [16] Toda mujer casada sabe acerca de la fidelidad de todos los hombres del Reino, excepto de su propio marido, y la etiqueta exige que a ninguna mujer se le diga acerca de la fidelidad de su marido. Además, un disparo en cualquier casa del Reino se oirá en cualquier otra casa. La Reina Josefina anunció que se había descubierto al menos a 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 se las arreglaban las esposas para lograr esto?
El problema de Josefina 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 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 clásico libro de texto 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 modo que todos los demás pudieran verla, pero ellos no. Había bandas de muchos colores diferentes. Todos los Lógicos se sentaron en círculo, y el Maestro les indicó que debía sonar una campana en el bosque a intervalos regulares: en el momento en que un Lógico supiera el color de su propia frente, debía irse al sonar la siguiente campana. Se les indicó que no hablaran, ni usaran un espejo o una cámara, ni 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 se fuera a tiempo sería expulsado bruscamente en el momento correcto. De manera similar, cualquiera que intentara irse temprano sería retenido bruscamente en su lugar y expulsado en el momento correcto. El Maestro tranquilizó al grupo afirmando que el rompecabezas no sería imposible para ningún Lógico Verdadero presente. ¿Cómo lo hicieron? [18]
Alicia en la convención de Lógicos es una inducción general más un salto de lógica.
Varios jugadores llevan 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 otros jugadores, pero no los de ellos mismos. Con una 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 basándose en los sombreros que ven y en lo que hacen los otros jugadores. En algunas versiones, compiten para ser los primeros en adivinar correctamente; en otras, pueden elaborar una estrategia de antemano para cooperar y maximizar la probabilidad de acertar. [19]
Una variación recibió nueva publicidad como resultado de la tesis de doctorado de Todd Ebert en 1998 en la Universidad de California, Santa Bárbara . [20] Es una pregunta de estrategia sobre un juego cooperativo , que tiene conexiones con la teoría de codificación algebraica . [21]
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 un círculo uno frente al otro. El primero que adivine correctamente el color de su sombrero gana.
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 es el sombrero 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. Por lo tanto, cualquier jugador que vea un sombrero azul puede adivinar de inmediato. Finalmente, el ganador se da cuenta de que, como nadie adivina de inmediato, no debe haber sombreros azules, por lo que todos los sombreros deben ser rojos. [22]
En el caso en que cada jugador tenga que adivinar, pero sea libre de elegir cuándo adivinar, 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 llevan sombreros azules ven B−1 sombreros azules y B sombreros rojos, por lo que esperan B −1 segundos y luego 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 adivinan correctamente al mismo tiempo.
Si B < R, entonces los que llevan un sombrero azul verán B −1 sombreros azules y R sombreros rojos, mientras que los que llevan un sombrero rojo verán B sombreros azules y R −1 sombreros rojos. Como B −1 < B ≤ R −1, los jugadores que llevan 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 donde R < B es similar.
Cuatro prisioneros son arrestados por un crimen , pero el juez ofrece librarlos del castigo si pueden resolver un acertijo de lógica. [23]
Tres de los hombres se colocan en fila. A mira hacia la pared, B mira hacia A y C mira hacia B y A. Un cuarto hombre se coloca detrás de una pared. Los cuatro hombres llevan sombreros; hay dos sombreros negros y dos sombreros blancos, cada prisionero lleva uno de los sombreros, y cada uno de los prisioneros solo ve los sombreros que tiene frente a él, pero no los que lleva sobre 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 la comunicación entre los prisioneros. Si algún prisionero puede averiguar de qué color es el sombrero que tiene en la cabeza con un 100% de certeza (sin adivinar), debe anunciarlo y los cuatro prisioneros quedan libres.
Los prisioneros saben que sólo hay dos sombreros de cada color. Por lo tanto, si C observa que A y B tienen sombreros del mismo color, C deducirá 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 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.
Al igual que muchos rompecabezas de este tipo, la solución se basa en el supuesto de que todos los participantes son lo suficientemente racionales e inteligentes como para hacer las deducciones apropiadas.
Después de resolver este rompecabezas, se puede obtener una idea de la naturaleza de la comunicación al reflexionar sobre si el silencio significativo del prisionero C viola la regla de "No comunicación" (dado que la comunicación suele definirse como la "transferencia de información"). [ cita requerida ]
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 otros dos, pero no el suyo. Cuando se le dé una señal, cada uno debe adivinar el color de su sombrero o pasar. Ganan la liberación si al menos una persona adivinó correctamente y ninguna se equivocó (pasar 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 codificación , por ejemplo, con códigos de Hamming . [24]
En una variante de este rompecabezas, los prisioneros saben que hay 2 sombreros negros y 2 sombreros blancos, y 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 a B, C y la pared, B ve la pared y C ve a B y la pared. (A nuevamente no puede ser visto y solo está allí 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 un prisionero lleva el sombrero de un color diferente. En el caso no trivial, dos de los cuatro prisioneros llevan sombreros del mismo color, mientras que A y C llevan los sombreros negros. Después de un tiempo, los cuatro prisioneros deberían poder deducir que, como D y B no pudieron decir el color de su propio sombrero, A y C deben llevar los sombreros negros.
En otra variante, sólo participan 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 atrás. Se les dice que habrá dos sombreros negros y tres sombreros blancos. A continuación, se coloca un sombrero en la cabeza de cada prisionero; cada prisionero sólo puede ver los sombreros de las personas que tiene frente a él y no en el suyo propio. El primer prisionero que sea capaz de anunciar correctamente el color de su sombrero será liberado. No se permite la comunicación entre los prisioneros.
Supongamos que A lleva un sombrero negro:
Entonces, si A usa un sombrero negro, habrá una respuesta bastante rápida de B o C.
Supongamos que A lleva 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ó, en total hay tres sombreros blancos y dos sombreros negros, y los tres prisioneros lo saben. En este acertijo, puedes asumir que los tres prisioneros son muy listos y astutos. 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, 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 desconocen el número de cada color. Los prisioneros se alinean en una sola fila, de modo que cada uno puede ver los sombreros que tiene delante, pero no detrás. Empezando por el prisionero que está al final de la fila y avanzando hacia adelante, cada uno, por turno, debe decir solo una palabra que debe ser "rojo" o "azul". Si la palabra coincide con el color de su sombrero, son liberados; si no, son asesinados en el acto. Un guardia comprensivo les advierte de esta prueba una hora antes y les dice que pueden formular un plan según el cual, siguiendo las reglas establecidas, 9 de los 10 prisioneros sobrevivirán con seguridad y 1 tendrá una probabilidad de supervivencia del 50/50. ¿Cuál es el plan para lograr el objetivo?
Los prisioneros acuerdan que si el primer prisionero ve un número impar de sombreros rojos, dirá "rojo". De esta manera, los otros nueve prisioneros sabrán el color de su 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, ya sea rojo o azul, pero los prisioneros desconocen el número de cada color. Los prisioneros se distribuyen en la habitación de tal manera que puedan ver los sombreros de los demás, pero no el suyo. Ahora, cada uno, simultáneamente, debe decir 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 pueden formular un plan siguiendo las reglas establecidas, 5 de los 10 prisioneros serán liberados definitivamente y podrán rescatar a los demás. ¿Cuál es el plan para lograr el objetivo?
Los prisioneros se forman en parejas. 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. Luego, si ambos usan 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 quién es A y quién es B, lo que puede no estar permitido.
Otra posibilidad es que los prisioneros formen 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. De manera similar a la variante con la audición, pueden deducir el color de su sombrero a partir de esta suposición. Exactamente un grupo tendrá razón, por lo que 5 prisioneros responden correctamente y 5 no.
Obsérvese 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 sombreros donde dice la respuesta correcta como donde no la dice. Por lo tanto, hay tantas distribuciones de colores de sombreros donde 6 o más prisioneros dicen la respuesta correcta que donde 4 o menos lo hacen.
En esta variante, un número infinito de prisioneros, cada uno con un sombrero rojo o azul desconocido y asignado aleatoriamente, se alinean en una sola fila. Cada prisionero está de espaldas al principio de la fila y puede ver todos los sombreros que tiene delante y ninguno de los que tiene detrás. Empezando 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 conocerse 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 manera de garantizar que solo mueran un número finito de prisioneros?
Si se acepta el axioma de elección y se supone que cada prisionero tiene la capacidad (irrealista) de memorizar una cantidad infinita e incontable de información y realizar cálculos con una complejidad computacional infinita e incontable , la respuesta es sí. De hecho, incluso si permitimos una cantidad incontable de colores diferentes para los sombreros y una cantidad incontable de prisioneros, el axioma de elección proporciona una solución que garantiza que solo un número finito de prisioneros debe morir siempre que cada prisionero pueda ver los sombreros de todos los demás prisioneros (no solo los que están delante de ellos en una fila), o al menos que cada prisionero pueda ver todos los 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 están en la fila forman una secuencia de 0 y 1, donde 0 representa el azul y 1 el rojo. Antes de que los pongan en la fila, los prisioneros definen la siguiente relación de equivalencia sobre todas las posibles secuencias 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 pone en su 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 incontable de comparaciones para encontrar una coincidencia, y que cada comparación de clase requiere un número infinito incontable de comparaciones de sombreros individuales). 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.
Como los prisioneros no tienen información sobre el color de su propio sombrero y harían la misma suposición sea cual sea el color, cada prisionero tiene un 50% de posibilidades de ser asesinado. Puede parecer paradójico que un número infinito de prisioneros tengan la misma probabilidad de ser asesinados y, sin embargo, sea seguro que solo un número finito de prisioneros sean asesinados. La solución a esta paradoja radica en el hecho de que la función empleada para determinar la suposición de cada prisionero no es Función medible .
Para ver esto, considere el caso de cero prisioneros asesinados. 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 como representaciones binarias de un número real entre 0 y 1, las secuencias representativas forman un conjunto no medible . (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 evento de cero prisioneros asesinados. 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 igual a la anterior, salvo que los prisioneros pueden oír los colores que dicen los demás prisioneros. La pregunta es: ¿cuál es la estrategia óptima para los prisioneros de modo que mueran la menor cantidad posible de ellos en el peor de los casos?
Resulta que, si se permite a los prisioneros escuchar los colores gritados por los otros prisioneros, es posible garantizar la vida de todos los prisioneros excepto del primero, que muere con una probabilidad del 50%.
Para ello, definimos la misma relación de equivalencia que antes y seleccionamos de nuevo 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 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 posible secuencia infinita con un 0 o un 1 con la importante propiedad de que cualesquiera dos secuencias que difieren en un solo dígito tienen etiquetas opuestas.
Ahora bien, cuando el alcaide 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. Dada esta información, todos los que están después de él 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 sabe, hay dos posibles secuencias que la primera persona podría haber etiquetado: una que comience con un 0 y otra que comience con un 1. Debido a nuestro esquema de etiquetado, estas dos secuencias recibirían etiquetas opuestas, por lo que, en función de lo que diga 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 su propio color de sombrero. De manera similar, cada persona posterior en la fila conoce todos los dígitos de la secuencia excepto el correspondiente a su propio color de sombrero. Conoce a los que están antes de él porque fueron nombrados, y a los que están después de él porque puede verlos. Con esta información, puede usar la etiqueta nombrada por la primera persona para determinar su propio color de sombrero. De esta forma, todos, excepto la primera persona, siempre aciertan.
La versión de Ebert del problema establece que todos los jugadores que adivinen deben hacerlo en el mismo momento predeterminado, pero que no todos los jugadores están obligados a hacerlo. Ahora bien, 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 los 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 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 de Hamming produce mayores tasas de victorias para valores mayores de N .
En esta versión del problema, cada intento individual tiene un 50% de posibilidades de ser correcto. Sin embargo, el método del código de Hamming funciona concentrando los intentos erróneos en determinadas distribuciones de sombreros. En algunos casos, todos los jugadores adivinarán incorrectamente, mientras que en otros casos, solo un jugador adivinará, pero correctamente. Si bien la mitad de todos los intentos siguen siendo incorrectos, esto hace que los jugadores ganen más del 50% de las veces.
Un ejemplo sencillo de este tipo de solución con tres jugadores es ilustrativo. Con tres jugadores, hay ocho posibilidades; en dos de ellas, todos los jugadores tienen el sombrero del mismo color, y en las otras seis, dos jugadores tienen un color y el otro jugador tiene el otro color.
Los jugadores pueden garantizar que ganen en los últimos casos (75% de las veces) con la siguiente estrategia:
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, sólo un jugador adivinará, y correctamente, que su sombrero es el opuesto al de sus compañeros. [25]
rompecabezas de sombrero todd.
