A las veinte preguntas en contra de un mentiroso

Question

Aquí está uno que apareció en mi mente cuando estaba pensando acerca de la búsqueda binaria.

Estoy pensando en un número entero entre 1 y n. Usted tiene que adivinar el número de mi. Usted gana tan pronto como usted adivinar el número correcto. Si su suposición no es correcta, me voy a dar una pista diciendo "demasiado alto" o "muy baja". ¿Cuál es tu mejor estrategia?

Este es un problema fácil si siempre les digo la verdad: por adivinar el (redondeado) media límite inferior y el límite superior, usted puede encontrar mi número en alrededor de registro₂n conjeturas en la mayoría de los.

Pero, ¿y si se me permite engañar una vez? ¿Cuál es tu mejor estrategia, entonces? Para aclarar: si usted adivina mi número, siempre gana al instante. Pero se me permite, en la mayoría de una vez, para decirte "demasiado alto" cuando su conjetura es demasiado baja, o al contrario. También puedo decidir no mentir.

Aquí está una áspera límite superior: usted puede pedir a cada número de dos veces para asegurarse de que yo no soy infiel, y si alguna vez me dan dos respuestas diferentes, acaba de pedir una tercera vez y, desde entonces, el juego el juego regular. De esta manera, usted puede ganar alrededor de 2 log₂n conjeturas en la mayoría de los.

Estoy bastante seguro de que el obligado puede ser mejorado. Alguna idea?

Answer 1

No es un simple estrategia que requiere (1 + ε)log(n) + 1/ε + O(1) las consultas, para cualquier constante ε > 0. Me ilustrar esta estrategia a continuación.

• En primer lugar, me pregunta si o no X, el número secreto, es n/2. Sin pérdida de generalidad, supongamos que la respuesta "menos". Aprendo nada en primer lugar, porque puede ser la mentira; pero por el momento le doy el beneficio de la duda.

• Me próximo preguntará si X es n/4. Si usted dice "menos", no sé si es o no 0 < X < n/4, pero me hacen saber que 0 < X < n/2, porque usted no puede mentir dos veces. Del mismo modo, si tengo que hacer un normal binario de búsqueda, siempre y cuando usted continúe a la respuesta "menos", yo sé que tu respuesta a la anterior consulta fue honesta. Así podremos reducir, para el caso en que se puede decir "más" a mi pregunta de si X es n/4.

• Si me siguen en tu palabra, llevar a cabo una búsqueda binaria, y preguntar acerca de si X es 3n/8, usted puede decir "más" o "menos". Si usted dice "más", entonces no sé si X > n/2, pero sí sé que X > n/4, otra vez, porque usted no puede mentir dos veces. Así que de nuevo siempre y cuando usted continúe a la respuesta "más" en la normal de mi búsqueda binaria, sé que su respuesta a la consulta anterior fue honesta.

De manera más general: si yo siempre te imagino en virtud de la hipótesis de que estás siendo honesto, en cualquier "monótono" secuencia de respuestas, sé que todos (posiblemente) el último de ellos son honestos. Por lo que podría parecer como si el peor escenario es donde tus respuestas alternativas mucho, como podría ocurrir, por ejemplo, si se hubiera elegido algo como X = _⌊ n/3 _⌋. Pero en la alternancia caso, puedo estar seguro de la honestidad de algunas de sus respuestas:

• Si usted dice (no monótona) que X es menor que 3n/8, no sé si X es menor que 3n/8 por seguro, pero sé que X < n/2, porque de nuevo no puede haber mentido acerca de ambos.

De manera más general: no sólo yo sé que monotónica subsecuencias de respuestas son en su mayoría honesto, sé que en cualquier momento en que usted responde "más" o "menos", su respuesta anterior de la misma especie también fue honesto. Lo que en realidad debería ser más sospechoso, cuando me encuentro mucho monótona de las subsecuencias en sus respuestas, que en la respuesta anterior a la que monotónica larga era una mentira.

Lo que necesito es una estrategia que me va a decir al volver a visitar a una vieja pregunta, dependiendo del tamaño de n es. Idealmente, retomando viejas preguntas requieren muy poca sobrecarga. Si me encuentro con una monótona secuencia de f(n) las respuestas, volver a la última pregunta antes de que la monótona secuencia de empezar.

• Por ejemplo, si sus respuestas a las consultas acerca de n/4, 3n/8, 7n/16, etc. son todos monótonamente "más", finalmente me pregunte acerca de la última vez que dijo "menos", que es para n/2, en caso de que mintió en ese entonces. Esto me permite evitar el escenario donde mentir acerca de n/2, y me incertidumbre en el apartado 2,^t-1 − 1)/2^t hasta que eliminar todas las posibilidades de captura, que en su mentira, y luego rehacer todos los de mi binarios de búsqueda para las consultas mayor que n/2.

Si tengo que hacer un doble chequeo como este cada vez que me encuentro con una monótona secuencia de longitud r, yo en el peor de los casos de consulta sobre (r+1)log(n)/r = (1 + 1/r)log(n) veces. Si yo te atrapo en una mentira, yo sólo han "gastado" r consultas, y mi estrategia después puede ser sólo una simple búsqueda binaria sin doble cheques; por lo que su estrategia óptima para maximizar el número de consultas que hago en realidad es no mentir en todo, o para guardar su mentira para casi el final del juego me costó cerca de r consultas adicionales. Aquí r puede ser arbitrariamente un gran número entero; por lo tanto para cualquier ε, puedo alcanzar una velocidad de consulta de (1 + ε)log(n) + 1/ε + O(1) mediante el establecimiento de r > 1/ε.

Bono problema #1. Sin demasiado trabajo extra, creo que se puede mejorar esto a una estrategia que sólo requieren log(n) + O(log log(n)) las consultas, pero soy demasiado perezoso para trabajar en los detalles ahora mismo.

Bono problema #2. Generalizar esta estrategia para el régimen en el que se le permite a mentir a mí un número fijo de veces que L > 0.

Answer 2

Mira esta respuesta en MathOverflow:

Sí, hay una manera de adivinar un número preguntar 14 preguntas en el peor de los casos. Para hacer esto usted necesita un lineal de código con una longitud de 14 de dimensión 10 y distancia de al menos 3. Un dicho código puede ser basado en el código de Hamming (ver http://en.wikipedia.org/wiki/Hamming_code).

Aquí está la estrategia.

Deje que nos indican los bits del primer número del reproductor como una_i, i ∈ [1..10]. Empezamos con la pregunta de los valores de todos los bits. Que se nos haga las siguientes preguntas: "¿es cierto que i-ésimo bit de su número es cero?" Deje que nos indican las respuestas a esas preguntas como b_i, i ∈ [1..10].

Ahora le pedimos a 4 preguntas adicionales:

Es cierto que un₁ ⊗ un₂ ⊗ un₄ ⊗ un₅ ⊗ un₇ ⊗ un₉ es igual a cero? (⊗ es sumation módulo 2).

Es cierto que un₁ ⊗ un₃ ⊗ un₄ ⊗ un₆ ⊗ un₇ ⊗ un₁₀ es igual a cero?

Es cierto que un₂ ⊗ un₃ ⊗ un₄ ⊗ un₈ ⊗ un₉ ⊗ un₁₀ es igual a cero?

Es cierto que un₅ ⊗ un₆ ⊗ un₇ ⊗ un₈ ⊗ un₉ ⊗ un₁₀ es igual a cero?

Vamos q₁, q₂, p₃ y p₄ ser respuestas a esas preguntas adicionales. Ahora, el segundo jugador calcula t_i (i ∈ [1..4]) --- las respuestas a esas preguntas con base en los bits de b_j que anteriormente se consiguió desde el primer jugador.

Ahora hay 16 maneras cómo los bits q_me pueden diferir de t_i. Vamos a d_i = q_i ⊗ t_i (por lo tanto, d_i = 1 fib p_i ≠ t_i ).

Permítanos hacer una tabla de todos los posibles errores y los correspondientes valores de d_i: la posición de error -> (d₁, d₂, d₃, d₄)

no hay error -> (0, 0, 0, 0)

error en b₁ -> (1, 1, 0, 0)

error en b₂ -> (1, 0, 1, 0)

error en b₃ -> (0, 1, 1, 0)

error en b₄ -> (1, 1, 1, 0)

error en b₅ -> (1, 0, 0, 1)

error en b₆ -> (0, 1, 0, 1)

error en b₇ -> (1, 1, 0, 1)

error en b₈ -> (0, 0, 1, 1)

error en b₉ -> (1, 0, 1, 1)

error en b₁₀ -> (0, 1, 1, 1)

error en q₁ -> (1, 0, 0, 0)

error en q₂ -> (0, 1, 0, 0)

error en q₃ -> (0, 0, 1, 0)

error en q₄ -> (0, 0, 0, 1)

Todos los valores de (d₁, d₂, d₃, d₄) son diferentes. De ahí que podamos encontrar donde fueron un error y por lo tanto, encontrar todos un_yo.

Respondida por falagar.