Acertijo similar al acertijo de los 100 prisioneros, pero diferente

Question

El acertijo es el siguiente:

$\qquad$ Hay $100$ prisioneros de pie en línea, cada uno con un número en su espalda. Los números son todos diferentes, y van desde $1$ hasta $101$ (es decir, falta un número). La persona en la parte trasera de la línea puede ver los números de los 99 prisioneros que están frente a él. El prisionero al frente de la línea no ve ningún número. Comenzando con el prisionero en la parte trasera, cada prisionero debe gritar el número en su espalda, pero cada número solo puede ser dicho en voz alta una vez.

$\qquad$El primer prisionero claramente solo tiene un $50$% de probabilidad de adivinar su número correctamente. Sin embargo, una vez que haya adivinado su número correctamente, los 99 prisioneros restantes tienen un $100$% de probabilidad de adivinar correctamente el número en sus espaldas.

¿Cuál es su estrategia para lograr esto?

Actualización:

Se me ha dado una pista de que la solución "no solo implica sumas módulo". Hay más en la solución que solo un truco modular.

Answer 1

El prisionero de atrás imagina otro detrás con el número faltante. Luego adivina el número que hará que la lista sea una permutación par de los números $1$ a $101$. La persona delante de él (asumiendo que la primera conjetura es correcta) conoce todos los números menos dos y puede seleccionar el que hace la permutación par. Cada prisionero a su vez tiene solo dos opciones (asumiendo que los gritos anteriores son correctos) y una de esas hará que la permutación sea par.

Segunda solución: la persona de atrás grita el número de la persona de adelante. Como no ha logrado declarar su número correctamente, no hay requisito de que los demás sean correctos.

Answer 2

Puedo pensar en una estrategia que funcione si se permite que todo el grupo de personas cometa como máximo un error (una suposición razonable, creo, dado que no importa qué estrategia use, el último tipo obtiene la respuesta correcta con una probabilidad de como máximo 0.5): hacer que el último tipo grite la suma módulo 101 de los dos números faltantes. Entonces, cada persona delante de él tendrá que elegir entre 3 números faltantes (habiendo eliminado los que ya se gritaron), y solo necesitan ver cuáles de los dos números, al sumarse, dan como resultado el número que gritó la última persona. Esto les deja con una sola posibilidad, que gritan. Nota: esto solo funciona porque para cualquier 3 números distintos (a, b, c), la suma de cualquiera de dos pares distintos de ellos no puede ser la misma (incluso si la suma es módulo algún número entero).

Answer 3

Supongamos que los números faltantes son $\left\{i,j \right\}$

La última persona selecciona aleatoriamente uno de ellos, digamos $i$ para gritar.

Al mismo tiempo, piensa en un enfoque de canal lateral para transmitir el otro número a todos. Por ejemplo, va a empezar a gritar el número $i$ en el segundo $j$.

Answer 4

Hay muchos acertijos de prisioneros y no está claro a cuál versión base te estás refiriendo. En una de las versiones que conozco (que es más general), la declaración es diferente, pero la solución también funciona para tu pregunta ya que es un caso especial. Involucra lo que creo que llamas "sumas módulo", por lo que me pregunto si esa versión es la versión base a la que te estás refiriendo. Dicho esto, al final de esta respuesta también exploro otras interpretaciones de la declaración del problema...

Sea $x_k$ el número en la espalda del prisionero $k\in\{0,\cdots,N-1\}$, y sea $s_k$ el número gritado. Los $N+1$ números son permutaciones de $\{0,\cdots,N\}$ (comienzo con un índice 0 en lugar de 1 como en tu declaración para aliviar los ajustes a la aritmética de módulo, pero el problema es equivalente). La estrategia es la siguiente:

1. el primer prisionero se sacrifica a sí mismo para dar a todos los otros prisioneros la información que necesitan gritando el módulo N+1 de la suma de los números que ven delante de ellos, es decir: $$ s_0=\left(\sum\limits_{j>1}x_j\right)\mod (N+1) $$
2. el segundo prisionero ahora sabe que: $$ \left(x_1+\sum\limits_{j>1}x_j\right)\mod (N+1)=s_0 $$ y así resuelve para $x_1$
3. el prisionero $k$ resolverá $$ \left(x_k+\sum\limits_{0k}x_j\right)\mod (N+1)=s_0 $$ porque, comenzando con $j=1$, saben que $s_j=x_j$

Para convencerte de que esto funciona, puedes consultar esta hoja de cálculo de Google que hice. Aparte del botón de randomización que llama a un script, toda la lógica está implementada como fórmulas y puedes comprobar que cada prisionero solo utiliza el conocimiento a su disposición, es decir los gritos previos (si los hay) y los números en las espaldas de los que están después de ellos. (En particular, para aquellos que no quieren confiar en el script, o si el script no está activo por alguna razón, simplemente puedes cambiar los valores aleatorios manualmente.)

Estoy un poco confundido por tu declaración de "cada número solo puede ser dicho en voz alta una vez", y dadas los comentarios y lo antigua que es tu pregunta, deduzco que esto se agregó para evitar que los prisioneros tuvieran una segunda oportunidad de decir un número si se equivocaban la primera vez. (Esto fue sugerido en una de las respuestas, pero el acertijo entonces es trivial ya que todos los jugadores pueden resolver con certeza en 2 suposiciones dado que solo hay 2 incógnitas cada vez.) Dicho esto, si realmente quisiste decir que un número específico solo podía ser llamado una vez, entonces la solución anterior puede ser ajustada haciendo que el primer prisionero grite $s_0^*=s_0+(N+1)$, que es un número que no puede estar en la espalda de ningún prisionero.

Si, por otro lado, la declaración del problema es que el primer prisionero solo tiene la opción entre dos números, es decir el número en su espalda o el número faltante, entonces te pediría que revisaras la declaración del problema:

• estudiemos el caso para el prisionero $k>0$. Suponiendo que todos los prisioneros, excepto el primero, pudieron adivinar correctamente $s_j=x_j, \forall 0 con certeza, entonces a $k$ le quedan dos números sin explicación: o bien $x^*$ y $x_k$ si $s_0=x_0$, o bien $x_0$ y $x_k$ si $s_0=x^*$.
• de cualquier manera, la información sobre cuál elegir debe ser codificada de alguna manera, pero los prisioneros anteriores no codifican nada: simplemente eligen $s_j=x_j$, lo cual ayuda para el registro pero no dice nada sobre esos dos valores.
• el único prisionero capaz de codificar esa información es el primero, y puede hacerlo si tiene un "lenguaje" lo suficientemente grande para codificar esa información (como en la primera parte de esta respuesta, en la que hay $N+1$ valores para elegir para expresar esa información).
• sin embargo, si la elección para ese prisionero es binaria entre $x^*$ y $x_0$, solo se puede transmitir un bit de información. Eso puede ayudar al prisionero 2 a tomar la elección correcta, pero no es suficiente para ayudar a todos los prisioneros siguientes.

Esto, por supuesto, deja la puerta abierta a algunos "trucos", como pasar información de otras maneras (por ejemplo, inflexión de voz, etc.), pero mi impresión es que la declaración correcta es de hecho aquella para la que la primera parte de esta respuesta proporciona una solución.