Adivina el número, con la mentira permitida

Estoy bastante seguro de que ustedes ya conocen el juego Adivina el número (parece haber bastantes preguntas aquí) donde Alicia piensa en un entero positivo y Bob intenta adivinarlo. Alice responde diciendo "Lo tienes", "Bajo", "Alto". La estrategia habitual que puede hacer Bob es hacer una búsqueda binaria que adivinaría el número en O (log n) conjeturas, donde n es el número en el que Alice estaba pensando.Adivina el número, con la mentira permitida

Siempre me he preguntado acerca de la variante en la que Alice podía mentir.

Supongamos que ahora se permite a Alice mentir un número constante de veces (conocido de antemano tanto para Alice y Bob), pero solo se le permitió mentir al responder "Alto", "Bajo" (es decir, si Bob adivina el número correctamente , ella tiene que admitir eso).

¿Todavía es posible que Bob pueda adivinar el número en O (log n) conjeturas?

¿Qué pasa si a Bob se le permitieron consultas adicionales como "¿Cuántas veces has mentido hasta ahora?" (que Alice tiene que responder con sinceridad)? ¿Siguen siendo posibles las consultas O (log n)?

EDITAR: ¿Qué pasa si el número de mentiras también fue O (logn), y las consultas adicionales fueron: ¿Ha mentido más de x veces? y Alice se le permitió mentir sobre ellos ...

Disculpas por la EDIT.

Fuente

2011-04-15 user127.0.0.1

Si el número de mentiras permitidas - digamos k - es fijo independiente de n, Bob puede simplemente hacer cada pregunta 2k + 1 veces y saldrá con O (log (n)). –

Simplemente siga cada pregunta "estándar" con "cuántas veces ha mentido" y cambie la respuesta en consecuencia. Resultado: se hizo la misma cantidad de preguntas como si Alice nunca mintiera. – pmg

Me encanta. Dos pensamientos inmediatos (1) ¿qué pasa con el mapeo del espacio basado en las probabilidades (2)? ¿Cómo se vería un esquema para tratar de identificar las respuestas incorrectas? –

Ejecuta el algoritmo de búsqueda binario habitual. O obtienes la respuesta o obtienes una incoherencia (un conjunto de candidatos vacío). Si obtienes una incoherencia, Alicia debe haber mentido al menos una vez. Reinicia la búsqueda binaria. A menos que me falta algo, después de O (k * log (n)) pasos obtendrá la respuesta (más un límite inferior sobre cuántas veces mintió). No necesita saber k a priori.

Fuente

2011-04-15 18:06:49 foxcub

Supongo que fue una tontería: una vez que terminas, sabes exactamente cuántas veces mintió.En cuanto a las optimizaciones, en el peor caso (determinista), no creo que pueda vencer a k * log (n), ya que Alice no tiene que mentir hasta la última pregunta en una corrida dada. Si puedes vencer esto con un algoritmo aleatorizado, no lo sé; es una buena pregunta – foxcub

Creo que la clave es poder seleccionar un mejor punto de partida (que el medio) para la próxima ronda una vez que obtenga un conjunto nulo. –

¡Gracias! Quería hacerlo simple, resultó ser demasiado simple :-) –

Creo que todavía está en O (log n), porque ha especificado que Alice solo puede mentir un número constante de veces. Esto significa que ella puede, como mucho, multiplicar la cantidad de conjeturas que hace Bob por una constante.

Imagine que Alice puede estar 5 veces. Ahora, no importa cuándo Alice miente, terminará teniendo que contradecirse a sí misma. Bob lo notará y puede comenzar su búsqueda binaria. Alicia también está restringida a estar dentro de las conjeturas O (log n), de lo contrario, Bob adivinará el número correctamente y Alicia pierde su oportunidad.

Entonces, en el peor de los casos, donde Alice miente cinco veces, cada/justo antes/Bob obtiene la respuesta, simplemente ha provocado que la búsqueda binaria de Bob tome 6 * (log n) suposiciones (cinco mentiras + una respuesta correcta), que sigue siendo O (log n).

Fuente

2011-04-15 18:07:20 Cephron

Gracias por la respuesta. –

más bienvenidos :) – Cephron

Adivina el número, con la mentira permitida

Respuesta

Cuestiones relacionadas