Juego de 9 bits, un acertijo sobre la teoría de la información o la criptografía

Question

Esta pregunta se la hicieron en una reciente entrevista, yo no resolverlo.

Supongamos que hay dos personas muy inteligentes Alice y Bob, participar en un juego, el juego se desarrolla como sigue.

1. Algunos ordenador generar aleatorio de 9 0/1 bits en una secuencia $C_i, i=1,2,3,...,9$.
2. Antes de las rondas de inicio, Alice echar un vistazo a la secuencia y los recuerdo a todos.
3. El juego cuenta con nueve rondas.
4. En el inicio de la i-ésima ronda, Bob introducir un bit (0 o 1) $B_i$, entonces Alice entrar a otro bit $A_i$. Si $A_i=B_i=C_i$ que gana la ronda, los demás pierden.
5. Alice y Bob sabe $A_i,B_i,C_i$ sólo después de que el resultado de esta ronda.
6. Todo el que me extremos, i+1 ronda se inicia, vaya al paso 4.

Alice y Bob podría desarrollar una estrategia antes del inicio del juego, pero durante el partido no se les permite comunicarse el uno con el otro.

Q1. Hay una estrategia para ganar al menos 6 rondas?

Q2. ¿Cuál es la solución óptima se mide por la expectativa de ganar rondas?

EDITAR:

Para T1, tengo algo de idea. Bob puede recibir información durante el mis-partido de la ronda.

$P_k$ el valor de la garantía de ganar rondas de total $k$ ronda.

Obviamente, $P_k \ge \dfrac k2$ al $k$ es incluso.

La estrategia es simple, $A_i := C_{i+1},B_{i+1} := A_i$, cuando i es impar. $A_i := C_i$, cuando i es par.

Y debemos tener las siguientes relaciones.

$P_{k+1} \ge P_k,P_{k+1} \le P_k+1$

Fácil de probar, $P_1=0, P_2=1$.

Al $k=3, 1=P_2 \le P_3 \le P_2+1=2$

Queremos testificar si $P_3$ 2.

Teniendo en cuenta la muy mala caso, la primera ronda no coincide. Bob sólo 1 bit de información, es imposible cubrir cada 2 bits caso.

Por lo $P_3=1$

$2=\dfrac42 \le P_4 \le P_3+1=2$, lo $P_4=2$.

$2=P_4 \le P_5 \le P_4+1=3$ , damos testimonio de si $P_5$ 3.

Yo vengo con una estrategia compleja.

Deje $B_1=1$ si $C_1=1$, entonces todo lo que se hace.

Si $C_1=0$, $A_1 := \text{most frequent bit in} \{C_2, C_3, C_4\}, B_2=B_3=B_4 := A_1$.

Si $C_2=C_3=C_4$, a continuación, hecho.

Si no son los mismos, supongamos $C_2=1,C_3=C_4=0$. Deje $A_2:=C_5, B_5:=A_2$, problema resuelto.

Answer 1

Otro post de solo pensamientos (por ahora): El valor predeterminado de la idea, como se ha señalado, es básicamente para Alice utilizar el primer bit de decirle a Bob si hay más de 1s o más 0s. Ahora, Bob puede estar equivocado varias veces, si solo se mantiene adivinando $A_1$. Pero cuando Bob lo hace mal, Alice bits puede ser tomado como un bit de información que se da a Bob.

La observación interesante es que desde que Alice sabe cuando Bob le va a salir mal, Alice podría hacer como en el anterior, pero también podría deliberadamente se equivocan principios de la transferencia de información adicional. Entonces, por ejemplo (basado en la estrategia) Bob puede saber que él estaba a punto de conseguir el siguiente poco mal (así que no hemos perdido nada), pero también alguna información adicional basada en el hecho de que Alice eligió para hacerlo mal temprano en lugar de esperar a Bob para equivocarse. Por ejemplo, esto podría ser usado para decirle a Bob que estaba a punto de conseguir los siguientes DOS bits mal (incluso teniendo en cuenta la información que Alice le han dado en el primer bit Bob le pongo mal). Entonces, por ejemplo, Alice podría equivocarse de nuevo durante ese próximo bits o dos para transmitir que se trata de algún tipo de escenario peor de los casos como 101010101. Esto es difícil de convertir en una estrategia real, pero me hace pensar que en realidad hay algo de estrategia para garantizar la 6. Ingenua de un límite superior en la cantidad de información dada por Alice es algo como $2^3 {8 \choose 2}$ ya que ella da 3 bits de información y se pueden obtener los bits de mal en dos de los últimos 8 bits. Y esta es una cantidad decente de más de $2^6$.

Answer 2

Esta es sólo una solución tentativa, no una respuesta completa. Aún así, se produce una expectativa de $6.076,$ mejor que cualquier llegó tan lejos.

Bob conjeturas $0$ hasta Alice indica lo contrario. Bob va a seguir uno de los dos protocolos:

1. Siempre que hace una suposición correcta, él hace de la misma supongo que en el siguiente ronda. (El Palo de protocolo.)
2. Siempre que hace una suposición correcta, que hace que el contrario supongo que en la siguiente ronda. (El Cambio de protocolo.)

En la primera ronda, Alice conjeturas $1$ si Bob debe seguir el Palo de protocolo, y $0$ si Bob debe seguir el protocolo de Cambios. Si Bob suposición es correcta, entonces Alice le ha dicho qué hacer. Si Bob supongo que es incorrecto, adivinaba $0$ en la vta $2.$ En las rondas después de la primera, cuando Bob hace una estimación incorrecta, Alicia, supongo que es lo que Bob debe adivinar en la siguiente ronda. He asumido que Alice siempre deben informar a Bob la respuesta correcta para la siguiente ronda. Esto parece correcto, de manera intuitiva, pero no acabo de ver cómo demostrarlo.

Yo no puedo ver ninguna manera de calcular la expectativa, pero la fuerza bruta, así que escribí una secuencia de comandos de python.

def stick(C):
    'Score if the Stick protocol is employed on C'
    # On round 0, Bob guesses 0 and Alice 1 so the round is lost
    # and Bob guesses 0 on round 1
    wins = 0
    Bob = '0'
    for k in range(1,9):
        if C[k]==Bob:
            wins += 1
        elif k < 8:
            Bob = C[k+1]  #Alice tells Bob what to guess 
    return wins

def change(C):
    'Score if the Change protocol is employed on C'
    # On round 0, Bob and Alice guess 0
    # If this is correct, Bob guesses 1 on round 1
    # If it is incorrect, Bob guesses 0
    wins = 0
    if C[0] == '0':
        wins = 1
        Bob = '1'
    else:
        Bob = '0'
    for k in range(1,9):
        if C[k]==Bob:
            wins += 1
            Bob = '1' if Bob == '0' else '0'
        elif k < 8:
            Bob = C[k+1]  #Alice tells Bob what to guess 
    return wins    

results = [ ]
for n in range(512):
    C = bin(n)[2:]
    C=(9-len(C))*'0'+C
    best = max(change(C),stick(C))
    results.append(best)

print('Worst', min(results))
print('Best', max(results))
print('Average',sum(results)/512) 

Esto produjo:

Worst 4
Best 9
Average 6.076171875

No puedo creer que alguien se supone que debe producir esta respuesta en una entrevista, a menos que se le permitió escribir un programa. Yo no estoy reclamando esta estrategia es óptima. Por el contrario, creo que puede ser refinado aún más. Tenga en cuenta que sólo garantiza $4$ gana.

Answer 3

Esto reemplaza mi respuesta anterior. Parece imposible que Alice para dar Bob 6 bits de información cuando ella tiene sólo 3 bits, de los 9 disponibles para hacerlo.

Q2 es bastante extraño que sea su enunciado con "medido por la expectativa" y que me dio una pista: esta respuesta se basa en la sincronización.

• Alice debe elegir después de que Bob, así que Alice sabe cuando Bob ha elegido.
• Alice y Bob saber el resultado de cada ronda "justo después de", así que Bob sabe cuánto tiempo le tomó a Alice para elegir.
• Una elección inmediata por Alice señales de 0 y un retraso en la elección de las señales de 1 a Bob.

Q1. Sí, hay una estrategia para ganar al menos 6 rondas.

El 9 rondas puede ser dividido en 3 grupos de 3. Alice utiliza la primera ronda de cada grupo de decirle a Bob las respuestas a las siguientes dos rondas.

Ronda 1: Bob elige al azar. Alice elige la respuesta a la ronda 2, el uso de la demora de la señal de la respuesta a la ronda 3.

Ronda 2: Bob y Alice tanto hacer la elección correcta.

Ronda 3: Bob y Alice tanto hacer la elección correcta.

Ronda 4: como la ronda 1, etc.

Esto se asegura de que siempre gana un mínimo de 6 rondas.

Q2. Sí, no es una solución óptima medida por la expectativa de el ganador de la ronda.

Yo estaba pensando acerca de cómo Alice también podrían utilizar el tiempo en las rondas 2 y 3 para evitar que el resultado de la ronda 4 aleatorio, cuando la simple respuesta me golpeó. Basado en la estrategia anterior, Alice puede informar a Bob la respuesta a cada una de las rondas, excepto en la ronda 1.

• Alice siempre hace la elección correcta.
• Alice utiliza los retrasos de decirle a Bob la respuesta a la siguiente ronda.

Esto significa que siempre win 8 rondas, y la primera ronda es de 0,5 oportunidad.

Si se considera incierto, de lo "justo después de" significa, Alice y Bob podría utilizar la ronda 1 para establecer el tiempo de respuesta del ordenador, por Alice la elección de inmediato. Eso significa que "tirar" una ronda y sólo 7 victorias están garantizados.

---

(Respuesta Original)

Creo que las respuestas son

Q1. No hay ninguna garantía de al menos 6 victorias.

Q2. No es una solución óptima de antemano la estrategia.

• Están de acuerdo en que Bob debe adivinar $0$ en cada juego hasta que Alice le dice de lo contrario.
• Mientras la corriente de bits es el mismo que Bob adivinar, Alice elige correctamente y se gana la ronda.
• Cada vez que Alice sabe que Bob supongo que va a fallar y perder la ronda, ella se aprovecha de esto para informar a Bob de los más frecuentes valor de los restantes bits, por la elección de ese valor.
• Bob, a continuación, cambia su elección.

Si Bob elige al azar, siempre $0$, o siempre $1$, en promedio, ser $4.5$ éxitos. Sólo puedo mostrar el resultado empíricamente, con el siguiente programa C.

El peor resultado único en mi prueba es$4$, pero el promedio es $5.70$

#include <stdio.h>
#include <stdlib.h>

#define TESTS 40
#define BITS  9

int main(void)
{
    int test, bit, round, count, guess, bob, alice, correct, sum;
    int arr[BITS];
    sum = 0;
    for(test = 0; test < TESTS; test++) {
        guess = 0;
        correct = 0;
        for(bit = 0; bit < BITS; bit++) {
            arr[bit] = rand() % 2;
        }

        for(round = 0; round < BITS; round++) {
            bob = guess;
            if(guess == arr[round]) {
                alice = arr[round];
            }
            else {
                count = 0;
                for(bit = round + 1; bit < BITS; bit++) {
                    count += arr[bit];
                }
                guess = 0;
                if(count * 2 >= BITS - round) {
                    guess = 1;
                }
                alice = guess;
            }
            if(bob == arr[round] && alice == arr[round]) {
                correct++;
            }
        }
        sum += correct;
        printf("%d ", correct);
    }
    printf("\nsum = %d, average = %.2f\n", sum, (float)sum / TESTS);
}

La salida del programa:

6 7 5 5 6 5 6 8 6 7 5 4 5 5 6 8 5 5 5 7 5 5 5 6 6 7 6 5 7 6 5 6 5 5 5 6 4 6 5 7
sum = 228, average = 5.70

Yo podría haber sembrado el PRNG pero no lo hizo.

Answer 4

No una respuesta. Algunos pensamientos, seguida de un ejemplo simple que muestra que los pensamientos no pueden ser del todo correcto.

Estaba pensando que quizás se podría llegar a límites superior por un razonamiento como el siguiente:

Fuzzy parte: Asumir las rondas se dividen en dos categorías, aquellos en los que Alice intenta ganar diciendo $A_j=C_j$, y la de aquellos en los que ella intenta enviar a Bob un mensaje acerca de qué hacer en rondas posteriores. Dicen que el número de rondas que ella intenta ganar es $w$.

Parte equivocada: Entonces ella sólo puede enviar a $9-w$ bits de información a Bob, así que ella sólo puede garantizar que él consigue $9-w$ rondas de derecho. Por lo tanto no pueden garantizar más que $\min(w,9-w)\le 4$ rondas de derecho.

Ejemplo de Estrategia: Decir $n$ es el número de $j\ge2$$C_j=1$. Alice dice $$A_1=\begin{cases}1,&(n>4), \\0,&(n<4), \\C_1,&(n=4).\end{casos}$$

Entonces Bob elige $B_j=A_1$ todos los $j>1$.

Si $X$ es el número de victorias esto garantiza $X\ge4$. Lo cual no contradice la conclusión de que el falso argumento anterior, pero muestra que el razonamiento no es correcto: Nos aseguramos de $X\ge 4$ con un solo bit de información.

La elaboracin $E[X]$ para esta estrategia parece un poco de combinatoria. Tal vez de varios bits...

Answer 5

Probablemente no sea la respuesta correcta, pero usted escribió:

Antes de que comience el juego, Alicia eche un vistazo a la secuencia y recuérdelos todos

y

Alice y Bob podrían desarrollar una estrategia antes del inicio del juego

Ya que ambos están antes de que comience el juego, Alice podría decirle a Bob la secuencia.

La ganancia esperada sería 9 de 9.