He estado tratando de resolver este enigma:
Digamos que estoy pensando en un número entre el 1 y el 100. Puedes hacerme 10 preguntas distintas de sí/no para adivinar el número, pero exactamente una de mis respuestas será una mentira y no te diré cuál.
¿Cómo se puede hacer esto?
Podemos hacerlo por fuerza bruta, asumiendo que
Podemos imaginar que nuestro oponente comienza eligiendo ambos en qué número está pensando y cuando en el juego va a mentir, combinando en un espacio de muestra de $100\times 10=1000$ resultados . Al final conoceremos las dos partes del resultado. Esto no hace que el problema sea más difícil: si tenemos una estrategia que produce el número secreto, también podremos deducir la posición de la mentira simplemente comparando las respuestas con lo que deberían haber sido.
En cada punto de la estrategia, digamos que hay
Esto significa que hay $nm+s$ diferentes resultados aún en juego. Para estar seguros de ganar necesitamos mantener la invariante de que $nm+s\le 2^n$ . Esto es ciertamente cierto - pero apenas - en el estado inicial donde $n=10$ , $m=100$ , $s=0$ .
En realidad, seamos generosos y permitamos que el opositor piense en $101, 102, \ldots, 124$ pero en ese caso no mentirá. (No necesitamos dile a él que es una opción, pero hace que la estrategia sea ligeramente más fácil de describir si imaginamos que este es el caso). Esto da un estado inicial de $n=10$ , $m=100$ , $s=24$ y entonces podemos mantener la invariante como $$ nm+s = 2^n $$ exactamente.
Una primera observación es que cada uno de los 100 (124) números posibles puede contar entre los $m$ o entre los $s$ (o ninguno), pero no ambos. Esto significa que tenemos libertad para adaptar nuestra pregunta de tal manera que lo que hacen a la $m$ números se elige independientemente de lo que hagan a la $s$ números.
Ahora, el caso fácil primero: Si $m$ es incluso , entonces hacemos una pregunta sobre la mitad de los $m$ números, y la mitad de los $s$ números. No importa si la respuesta es sí o no, ahora estamos en una situación en la que $$ m_{\rm new} = m/2 \qquad s_{\rm new} = s/2 + m/2 $$ que corta exactamente $nm+s$ por la mitad: $$ (n-1)m_{\rm new} + s_{\rm new} = nm/2 - m/2 + s/2 + m/2 = \frac{nm+s}2 $$
El caso en el que $m$ es impar es un poco más complicado. Entonces no podemos hacer ninguna pregunta que corte $m$ por la mitad. Dividámoslo lo más equitativamente posible y hagamos una pregunta que mencione $\frac{m+1}2$ de ellos. Entonces, en el caso del "sí", terminamos con $ m_{\rm new} = m/2 + \tfrac 12 $ que contribuye más que antes a la $(n-1)m_{\rm new}$ término, por lo que tenemos que preguntar por el correspondiente menos que $s/2$ de los resultados únicos para mantener la $mn+s=2^n$ invariante.
Sin embargo, ¿podemos hacerlo? El riesgo es que $s$ es tan pequeño que no podemos dividirlo de forma desigual para corregir la división desigual de $m$ . Si preguntamos por $x$ de la $s$ números, obtenemos $$ s_{\rm new} = x + (m-m_{\rm new}) $$ y así podemos resolver para $x$ para encontrar $$ (n-1)m_{\rm new} + s_{\rm new} = \frac{nm+s}2 \iff x = \frac{s-n+2}2 $$ Será automáticamente un número entero (dado que $m$ era impar, $s=2^n-mn$ tendrá la misma paridad que $n$ ), pero también tiene que ser no negativo que es el caso si $s\ge n-2$ .
¿Existe el riesgo de que $s<n-2$ ? Esto sólo puede ocurrir si $m$ es $\lfloor 2^n/n\rfloor$ -- pero el más pequeño $n$ para el que ese número es impar es $12$ (los siguientes son $18$ y $25$ ), por lo que no es posible que se dé ese caso en el que $n$ comienza en $10$ .
Así que la estrategia funcionará.
Esto se generaliza a problemas de la forma
Pregunte a $n$ preguntas para adivinar una de $m$ números, dado que el oponente miente exactamente una vez.
Está claro que es un necesario condición para que esto sea solucionable que $nm\le 2^n$ . El caso más pequeño en el que esto (y la estrategia anterior) no es suficiente es $n=12, m=341$ En el análisis anterior vemos que, independientemente de la pregunta que hagamos primero, el "sí" o el "no" nos llevarán a tener demasiados resultados posibles en el siguiente paso.
Si conseguimos pedir al primero Sin embargo, el hecho de que $s$ obtiene una nueva contribución de aproximadamente la mitad de $m$ en cada paso significa que nunca más tendremos que preocuparnos por $s$ ser demasiado pequeño.
Todavía sin resolver: ¿Es posible pasar si tenemos que hacer todas nuestras preguntas simultáneamente sin ver ninguna respuesta (y las preguntas no pueden referirse explícitamente a qué respuestas se dan para otras preguntas o dónde está la mentira)?
Intuitivamente lo dudo; eso necesitaría un empaquetamiento extremadamente eficiente de grupos de 10 puntos en el hipercubo de 10 dimensiones de posibles secuencias de respuestas.
Esta variante ha ganado algo de atención en los comentarios y en otras respuestas. Creo que arrojará algo de luz sobre la pregunta original, así que daré una respuesta aquí.
¿Es posible pasar si tenemos que hacer todas nuestras preguntas simultáneamente sin ver ninguna respuesta (y las preguntas no pueden referirse explícitamente a qué respuestas se dan para otras preguntas o dónde está la mentira)?
La respuesta es que sólo podemos hacerlo si fuera de $80$ números posibles, $100$ es demasiado. Por tanto, cualquier estrategia a la pregunta original debe adaptar las preguntas en función de las respuestas obtenidas.
Esencialmente, todas nuestras preguntas son "¿Está el número en el conjunto $S_i$ ?" para $i=1,2,\dots,10$ y elegimos los conjuntos $S_i$ antes de conocer las respuestas a estas preguntas. Para cada número de $1,\dots,100$ creamos un código binario en el que el $i$ indica si el número está en el conjunto $S_i$ . Cuando escribimos las respuestas, obtenemos otra palabra binaria, y como hay exactamente una mentira, sabemos que la palabra difiere de la palabra clave de la respuesta correcta exactamente en 1 posición.
(En lo que queda, el distancia entre dos palabras clave es el número de posiciones en las que difieren).
Entonces, nuestra tarea es encontrar un conjunto $C$ de palabras de código para que ninguna palabra binaria esté a distancia $1$ de dos palabras clave diferentes. Esto equivale a la condición de que no haya dos palabras clave que tengan una distancia exacta $2$ .
Podemos dividir el conjunto $C$ a dos partes, $C_e$ contiene todas las palabras clave con un número par de $1$ s, y $C_o$ que contiene todas las palabras clave con un número impar de $1$ s. Ninguna palabra clave en $C_e$ está a la distancia $2$ de una palabra clave en $C_o$ Así que lo que queda es comprobar la condición de $C_e$ y $C_o$ por separado. Además, la distancia entre dos palabras de código en $C_e$ (y en $C_o$ ) nunca es impar. Por lo tanto, la condición es que la distancia mínima entre dos palabras de código en $C_e$ (y en $C_o$ ) es $4$ .
El tamaño máximo de un código binario de longitud $n$ y la distancia mínima $d$ viene dada por la función teórica de codificación $A(n,d)$ . En particular, $A(10,4)=40$ . Por lo tanto, el tamaño máximo para ambos $C_e$ y $C_o$ es $40$ . Por lo tanto, $|C|\leq 80$ . El límite puede alcanzarse tomando un código binario de longitud $9$ y la distancia mínima $3$ con $40$ y crear dos palabras de código a partir de cada una de ellas, añadiendo un $0$ y un $1$ al final. He aquí un ejemplo.
Para cada $n$ del 1 al 10 pregunte "¿Es Sha-512 (tu número|n) par?" Ahora, para cada uno de los números $z$ de 1 a 100 y cada $n$ de 1 a 10, comprueba si Sha256(z|n) es par. Cuando $z$ es su número, coincidirá con sus respuestas en exactamente 9 casos. Otros números coincidirán en una media de 5 números, ya que Sha-512 modela un oráculo aleatorio .
Aunque el media número de respuestas correctas para cada una de las 99 respuestas erróneas es sólo 5, el esperado número de aciertos falsos de "9 derechos" además de la respuesta correcta debe ser $99\binom{10}{9}2^{-10}=0.97$ .
Para un oráculo aleatorio, la probabilidad de que sólo haya uno de los 100 números que coincida exactamente con 9 de las respuestas es sólo del 38%.
No estoy seguro, si no he cometido alguna falacia aquí, pero si alguien ve una, entonces siéntase libre de señalarla y trataré de arreglarla.
Digamos que estoy pensando en un número entre 1 y 100. Puedes hacerme 10 preguntas distintas de sí/no para adivinar el número, pero exactamente una de mis respuestas será una mentira y no te diré cuál.
La respuesta a este acertijo parece ser muy sencilla: está obligado a mentir en la primera pregunta.
¿Por qué? Porque, para adivinar el número, podemos hacer 10 preguntas.
No tenemos que hacerlo. Podemos hacerlo. Así, no tenemos que hacerlo.
Por eso podemos hacer menos preguntas y la persona que responde no sabe cuántas preguntas vamos a hacer en realidad, así que como la persona que responde nos asegura que exactamente una de las respuestas será mentira, y somos libres de hacer exactamente una pregunta, tiene que ser la primera. De lo contrario, sus palabras no se sostendrían y podría acabar incumpliendo lo que ha dicho:
exactamente una de mis respuestas será una mentira
Además, hay que tener en cuenta que no estamos haciendo preguntas para determinar el número, sino para adivinar un número, por lo que no necesitamos al menos siete preguntas que se requieren para determinar siempre uno de $N$ números, donde $2^7 \ge N \ge 2^6+1$ (podemos escribir el número en sistema binario, es decir, utilizando 7 bits, siendo cada uno de ellos o bien 0 o bien 1, podemos escribir todos los enteros del 0 al 127; así, si el contestador dijera siempre la verdad, podríamos hacer una pregunta por bit y conocer la respuesta en 7 preguntas).
Bueno, parece demasiado fácil así, así que vamos a profundizar en el problema, con el supuesto adicional de que en realidad estamos obligados a hacer 10 preguntas.
Tenemos que hacer 10 preguntas, para adivinar el número, pero no hay nada que nos restrinja de qué tratan las preguntas, aparte de que sean preguntas de Sí/No.
Así, no tenemos que preguntar sobre los números que estamos tratando de adivinar. Podemos ignorarlo completamente y la persona que responda a nuestras preguntas tiene que estar preparada para ello. Por ejemplo, podemos preguntar, si esa persona es mayor que nosotros, si le gustan las rosas (a menos que no sea una pregunta de sí/no para esa persona) o cualquier otra cosa que queramos, incluyendo preguntas sobre las preguntas anteriores y si las respuestas en ellas eran verdad o mentira.
Así pues, supongamos que hacemos 7 preguntas para determinar la forma binaria del número que adivinamos, y que el contestador mintió al responder a una de estas preguntas, por ejemplo la número 3. Ahora, supongamos que le preguntamos, si mintió en una de estas preguntas y coincide con la pregunta, mientras que answerinag en la que realmente mintió:
"¿Mentiste al responder a la tercera pregunta?"
Como afirmó que "exactamente una de mis respuestas será una mentira y no le diré cuál", no puede responder a esta pregunta. Ya ha mentido y no puede responder "sí", por lo que se ve obligado a no responder a esta pregunta... que está bien.
No pasa nada, porque en el acertijo se dice que mentirá, al contestar una de ellas, es decir: no pasa nada por no contestar una pregunta o decir la verdad, siempre y cuando haya exactamente una pregunta en la que haya mentido al contestar.
Sin embargo, si el acertijo estuviera redactado de forma que respondiera a 9 preguntas con la verdad y mintiera exactamente en una, entonces tendríamos un gran problema:
¿Qué pasaría si le hacemos una primera pregunta, a la que responde con la verdad, pero luego seguimos preguntando en $N$ -a la pregunta de si su respuesta sobre $(N-1)$ -¿La pregunta era una mentira? En algún momento, tendría que mentir y no puede mentir en absoluto en la segunda, tercera, ..., novena pregunta, porque podríamos preguntarle en la siguiente pregunta si mintió en la anterior, lo que le impediría responder en esta pregunta.
Por lo tanto, tiene que mentir en la primera o en la última pregunta, pero no puede mentir en la primera, ¿qué pasa si le preguntamos sobre la mentira en la primera pregunta en una de las últimas preguntas? Entonces, está obligado a mentir en la última pregunta, pero entonces se determina que va a mentir ahora, lo que podemos incluir en nuestra pregunta y aunque no haya mentido todavía, podemos provocar una contradicción (paradoja del mentiroso) o hacer que una respuesta confirme que está mintiendo en la última pregunta, lo que va en contra de lo que dijo al principio, por lo que o bien no puede mentir o bien no puede responder a la pregunta, por lo que no ha mentido en ninguna de las preguntas.
Así que, en esta forma, el acertijo se contradiría a sí mismo y no tendría solución.
Pero, volvamos a la versión del acertijo que estamos analizando y sobre la que intentamos responder.
Las preguntas tienen que ser distintas, pero esto se puede conseguir mediante la conjunción lógica de alguna tautología (como "2>1" o así) con una pregunta sobre una de las respuestas anteriores, donde siempre preguntamos sobre la misma pregunta principal, mientras que la distinción está garantizada gracias a que usamos una tautología diferente cada vez que preguntamos.
Por lo tanto, si dijera la verdad en las primeras preguntas, existe la posibilidad de que no pueda responder al resto de las preguntas, ya que, como se indica en el acertijo, no puede decirnos que ha mentido en una pregunta determinada y nosotros podemos, aunque sea por casualidad, seguir preguntándole sobre la mentira en la misma pregunta en la que mentiría, al tiempo que preservamos que las preguntas sean distintas al conjuntar nuestra pregunta principal con tautologías únicas cada vez.
Por ejemplo, si respondió con la verdad a las primeras 5 preguntas, entonces (casualmente) preguntamos "¿Es su respuesta en la sexta pregunta una mentira?", que es una pregunta de sí/no, ya que su respuesta es una mentira o no es una mentira, pero por lo que hacemos aquí, no puede mentir. Él puede responder "no", lo que será cierto, también puede no responder, pero si él fuera a responder "sí", si no sería una mentira: https://en.wikipedia.org/wiki/Liar_paradox
Así que, él si se ve obligado a evitar que algo así pueda suceder (¡exactamente una respuesta tiene que ser una mentira!), por lo que mentirá antes.
Por eso tiene que mentir en la primera pregunta, porque si no miente entonces, podemos evitar que mienta.
Pero... ¿y si hacemos lo mismo con la primera pregunta y le impedimos mentir también ahí? ¡Entonces no puede mentir en absoluto!
Contradicción. El enigma no se puede resolver.
Eventualmente, podemos hacer una suposición extra, no estoy seguro de cómo formularla, pero lo que quiero decir es: prohibimos preguntar, si la respuesta para una pregunta actual es una mentira o no. Entonces, a menos que me haya perdido algo, lo más probable es que pueda mentir siempre que quiera, lo cual es problemático y probablemente requeriría que encontráramos alguna forma inventiva de hacer preguntas, para poder determinar realmente el número, pero no estoy seguro de cómo proceder con esto ahora. Voy a tratar de encontrar alguna manera fácil y editar la respuesta más tarde, pero demasiado cansado para hacer esto ahora.
No sé, si el hecho de contradecir el acertijo anterior, si lo hice correctamente, te servirá de algo, pero espero que sea la respuesta correcta para esta pregunta, es decir: es un acertijo irresoluble.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
¿Es necesario que estas preguntas sean de tipo sí/no?
0 votos
@SamCoutteau No
1 votos
Si las preguntas no tienen que ser sí/no, basta con preguntar "cuál es el número + n" 10 veces. La pregunta sólo es interesante si la restringes a sí/no.
0 votos
@DanielV ¿Qué es n? Oh te refieres a 1) "¿Qué es el número + 1?" 2 ) "¿Qué es el número +2?" etc. Tienes razón
0 votos
@DanielV Sin embargo, son esencialmente la misma pregunta, ¿no? Uno sigue usando la ley del medio excluido, ¿y si está prohibido usarla?
1 votos
Voy a suponer que estás interpretando mal la pregunta que te han hecho. Lo de "no puedes usar LEM" probablemente quiere decir: "¿Es el número mayor que 50?" "No" Entonces no puedes deducir que es menor que 50 (LEM) porque no sabes si esa respuesta era mentira. Probablemente no significa que no puedas usar LEM en general (qué cosa más absurda), sólo que no puedes asumir un sí/no binario porque esa podría haber sido la pregunta que era la mentira.
4 votos
Esto va a necesitar una codificación inusualmente eficiente. Una vez fijada la estrategia del preguntador (es decir, la regla para saber qué pregunta hacer en cada momento, dadas las respuestas anteriores), hay 10 patrones diferentes de respuestas que podemos obtener para cada uno de los 100 números, lo que significa que tenemos que reconocer 1000 patrones de respuesta en total. Esto se aproxima mucho a la $2^{10}=1024$ diferentes patrones de respuesta que es posible dar. Así, por ejemplo, la estrategia debe ser tal que en la mayoría de los casos adivinar mal si resulta que las diez respuestas eran honestas.
0 votos
Aquí hay un simulador: repl.it/repls/ProperDraftyQuoll
1 votos
Además, soy capaz de llegar hasta 64 sin una función hash.
0 votos
Sí. Un código Hamming acortado da fácilmente una solución para el rango $[1,64]$ . El comentario de @Henning lo hace interesante.
1 votos
He aquí una estrategia no adaptativa para el 72 (encontrada mediante búsqueda codiciosa) pastebin.com/kebm2CPp
0 votos
Para el caso estático/no adaptativo, la única restricción es que no hay dos palabras de código que tengan una distancia exacta $2$ . De forma equivalente, las palabras clave pares forman un código con una distancia mínima $4$ y también las palabras clave de impar. Por lo tanto, el número máximo de palabras de código es $2A(9,3)=80$ .