¿Cuántos científicos pueden sobrevivir?

Question

Ayer los extraterrestres tomaron 100 científicos de la Tierra como prisioneros. Quieren poner a prueba qué tan inteligente es el de los humanos.

Los extranjeros hizo 101 diademas, numerados de 1 a 101. En el día del concurso, se tiran una de las bandas para la cabeza, y luego del resto de las bandas para la cabeza de forma aleatoria poner uno en cada uno de los científicos. Luego de que la línea de los científicos en una cola de tal manera que cada persona puede ver los números escritos en las bandas de las personas que están de pie delante de él, pero no puede ver su propio número, ni el número de los científicos detrás de él.

A continuación, los alienígenas obligará a los científicos a adivinar sus números, y después de que todos se terminó diciendo un número, van a matar a los que dijo que un número diferente de lo que está escrito en sus diademas. Tenga en cuenta que cada científico sólo puede decir un número en el rango de 1-101, y nadie puede decir un número que ya ha sido dicho. Cada científico independiente puede optar a la hora de hablar de su valor; no hay ningún pre-orden establecido en cuando tienen que hablar. Como son muy inteligentes, los científicos pidieron a encontrar una manera de salvar a la mayoría de ellos. Encontramos de esta manera, y luego probarlo.

Answer 1

Usted puede guardar el 99,5 científicos.

Imagino que la 101ª diadema fue dejada en el suelo por detrás de la primera científico, haciendo una línea de 101 bandas para la cabeza.

La estrategia es que cada uno debe asumir que las bandas se colocan en una permutación de los números {1, 2, ..., 101}. Cada científico siempre tendrá una opción de dos bandas para la cabeza: uno de los resultados de una permutación y uno de los resultados en una permutación impar. Siempre hacen la elección que se traduce en una permutación.

Si las bandas son en realidad en una permutación (la mitad del tiempo), todo el mundo adivina correctamente. (Más formal inductivo de la prueba a continuación.)

Si las bandas son en realidad en una permutación impar, a continuación, el primer científico que está muerto. Pero el resto de los científicos todavía están guardados: van a terminar de nomenclatura de una permutación que es correcto excepto para el interruptor de la primera científico de la banda con uno sobre la tierra.

La prueba de que todo el mundo adivina correctamente si las bandas son en realidad en una permutación:

Considerar el primer científico. Él puede ver el 99 bandas para la cabeza, así que sabe que sólo hay dos posibles arreglos. Estos acuerdos están relacionados por una sola swap (intercambio de la banda de su cabeza para la izquierda en el suelo), por lo que uno de ellos es una permutación y el otro es impar. Su estrategia es decir, el número que corresponde a la permutación, y estamos asumiendo aquí que, en realidad, es incluso una permutación, por lo que su suposición es correcta.

Ahora considere el enésimo científico. Podemos asumir, por inducción que la primera (n-1), los científicos han adivinado correctamente, y se puede ver a una mayor (100-n) cintas para la cabeza. Así que él sabe que un total de 99 números. Esto significa que, de nuevo, sólo hay dos posibles arreglos, y los dos acuerdos están relacionados por una sola swap (intercambio de la banda de su cabeza por la de la planta). Así que, precisamente, uno de estos arreglos es una permutación, y este es el que la enésima científico va a adivinar. Esto significa que la enésima científico también ha adivinado correctamente, ya que sabemos que la disposición real es de permutación.

Answer 2

El científico en la parte posterior indica la suma de todos los 99 números visibles, $S_ {99} $. Él o ella morirá. El segundo al último científico es ojala lo suficientemente listo como para comprender por qué el científico previo claramente recogido un número defectuoso. Este científico ahora se puede sumar los 98 números visibles, $S_ {98} $, determinar únicamente su propio número, $S_ {99} - S_ {98} $.

Esta idea se repite, todos los científicos restantes del ahorro.

Todos menos uno sobreviven.

Answer 3

Edit: por Desgracia, se me olvidó que $\oplus$ sólo está garantizada para mantener con nosotros en el número de bits, pero que aún podemos llegar más alto. En su lugar, vamos a tratar con la aritmética modular.

Supongamos que tenemos prisioneros de $N_1,\ldots,N_n$, donde sus números son de $n_1,n_2,\ldots,n_n$ (es decir, $n_i$ es el número del científico). Para mis propósitos, supongamos que hemos de extraer de la gama de $0, \ldots, n$ en lugar de $1, \ldots, n+1$ (es trivial para convertir de un rango a otro). También, vamos a definir el orden de los prisioneros tal que $N_i$ puede ver todos los $N_j$ tales que $i>j$. Además, definir el operador $\%$ tal que $a\mathbin{\%}b = c$, donde $c \equiv \mod b$ y $c \in \{0,\ldots,b-1\}$. Bien.

Científico de $N_n$ calcula $A_n=(\sum_{i=0}^{n-1} n_i)\mathbin{\%} n$ y dice eso.
Científico de $N_{n-1}$ calcula $(A_n - (\sum_{i=0}^{n-2} n_i))\mathbin{\%} n = n_{n-1}$ y dice eso.
Científico de $N_j$ calcula $(A_n - (\sum_{i=j+1}^{n-1} n_i) - (\sum_{i=0}^{i-1} n_i))\mathbin{\%} n = n_j$

Y así, cada Científico extractos de su número. Esto resulta en un mínimo de $98$ científicos, desde $99$ averiguar sus números, pero uno podría decir que el número dicho por $N_n$. Tenga en cuenta que hay una posibilidad, aunque pequeña, de que la totalidad de los $100$ científicos.

---

El OP dice que hay una manera de ahorrar $99$ científicos. Esto requeriría $N_n$ a de alguna manera de codificar los $2$ números a los que puede ver en uno de esos $2$, de modo que $N_{n-1}$ se puede averiguar su número. No estoy seguro de cómo hacer esto...

Answer 4

Antes de la primera persona la que habla la segunda persona tiene tres posibles opciones $a<b<c$ vamos a encontrar una manera para que la primera persona que hace la otra persona que tiene la respuesta correcta (por supuesto, la primera persona que conoce las tres opciones, la otra persona puede tener, que son a,b o c. Lo que vamos a hacer es que si la segunda persona tiene $un$ dice $b$, si la segunda persona que ha $b$ dice $c$ y si la segunda persona que ha $c$ dice $a$. Si la persona $1$ hace esto, se puede guardar persona $2$, la persona $3$ puede hacer esto para salvar a la persona $4$ y así sucesivamente. Yo no creo que este sea óptimo, pero puede ayudar. Este método podría ahorrar la mitad de la gente cuando $n$ es par y un poco menos de la mitad cuando $n$ es impar.

Answer 5

Podemos ahorrar $m$ científicos con $m$ que se determina a continuación - y probablemente más. Los números de la primera $m$ científicos se sabe que la parte de atrás de $100 m$ científicos. De ahí que todos conocen la $101-m$ números distribuidos entre ellos y el cubo de la basura. Cómputo de una permutación de estos $101-m$ números y anunciar los primeros $100-m$ estas en el fin de así obtenida. Esto les permite transmitir $\log_2((100-m)!)$ los bits de información adicional a la parte delantera $m$ personas codificados en la permutación. Ahora cada una de las delanteras $m$ científicos de la necesidad de elegir entre dos posibles números, los dos únicos números que no se han enterado y no visto por ella. Para tomar una decisión, ella se extrae un poco de información adicional. Con el fin de lograr que la totalidad de los $m$ puede extraer un poco, nos necesitan $$ 2^m\le (100-m)!$$ Esto es que si dejamos a $m=76$.

La permutación de $25 dólares de los números que los $24$ de vuelta a los científicos calcular a partir de la observación de los primeros $m$ científicos pueden ser considerados aleatorios, por lo tanto, tiene un punto fijo en la media y $\frac{24}{25}$ de esto son los científicos de ser salvos. Así

76 científicos garantizados para ser salvos

76.96 científicos guardan en promedio