Me dijo mi profesor de computación que si hemos generado al azar de n-bits cadena binaria (usaré $n=9$ para este ejemplo) que siempre puede ser adivinado en 6 o menos conjeturas siempre que inicialmente se conoce la cantidad de 1's y 0's en el número, y después de cada supongo que nos dice el número de bits que nos imaginamos en la posición correcta. Entiendo las permutaciones sería $9\choose x$ donde $x$ es el número de 1's en la cadena. Pero con 126 permutaciones de cadenas que contiene 4 1 (5 1) ¿cómo podría esto ser hecho en 6 conjeturas?
Respuesta
¿Demasiados anuncios?
Thanassis
Puntos
66
Te voy a mostrar cómo usted puede encontrar una generados al azar 9-cadena de bits con 6 conjeturas o menos, si usted sabe que hay cuatro 1 bits y cinco 0 bits y después de cada supongo que te dicen cuántos bits tienes derecho (pero no la que los bits).
Se han identificado correctamente que hay $126$ 9-cadenas de bits que contienen exactamente cuatro 1 bits. Usted se está preguntando cómo se puede distinguir entre estos $126$ cadenas posibles con solo 6 aciertos. Tener 6 conjeturas no quiere decir que sólo podemos comprobar 6 permutaciones al azar y esperanza tenemos suerte. Estamos recibiendo información valiosa después de cada adivinar y esto puede guiar nuestra búsqueda.
Una observación clave es que si nuestras conjeturas contener el número correcto de 1s (es decir, cuatro 1 y cinco 0), a continuación, el sólo posibles respuestas para adivinaron correctamente los bits son: $9,7,5,3,1$. Esto podría no ser evidente al principio, pero aviso de que si cambiamos el valor de un bit (decir $0\rightarrow1$), entonces tenemos que cambiar algunas otras bits $1\rightarrow0$ en el fin de mantener el número de unos y ceros en la cadena. Otra forma de pensar, es que solo se nos permite el intercambio de bits que tienen valores distintos (no hay punto de intercambio de bits que tienen el mismo valor, porque nada iba a cambiar). Así que si tenemos todos los 9 bits de corregir y hacer un swap, vamos a terminar con 7 bits correctos. Si luego nos swap sólo un poco de lo que es incorrecto, vamos de nuevo de 7 bits correctos. Si cambiamos de dos bits correctos bajamos a 5 bits correctos, y así sucesivamente.
Voy a presentar una solución en la que nuestras conjeturas siempre contienen el número correcto de 1s y 0s. Esto no significa que las otras soluciones (no cumplir esta restricción) no existen.
Una respuesta de 9 bits correctos, significa que estamos hecho, así que sólo tenemos que decidir qué hacer cuando se obtiene una respuesta de $7,5,3,1$ bits correctos. Voy a romper la estrategia de los casos, de acuerdo a lo que es la respuesta a nuestra primera conjetura. Con el fin de ayudar a la discusión, imaginar que tenemos que encontrar la (desconocida para nosotros) cadena de destino $001111000$. Vamos a examinar en primer lugar el caso cuando nuestra primera conjetura devuelve una respuesta de $1$ bit correcto. Quizás sorprendentemente, este es el caso más fácil de manejar.
Adivina primero devuelve 1 bit correcto
Esto significa que el único bit correcto tiene que ser un 0. Así, sabemos inmediatamente que todos nuestros 1 bits son incorrectos y que tiene que ser cambiado. Yo la uso específico de los bits de la cadena de ejemplos para describir cómo proceder en cada caso, pero esto no los de la generalidad de la solución. Con el fin de mostrar nuestro conocimiento sobre los bits después de cada respuesta, voy a utilizar el siguiente código de colores:
- $\color{green}{\text{green}}$ dígitos son aquellas que sabemos que son correctas (valor correcto en la posición correcta),
- $\color{red}{\text{red}}$ dígitos son los únicos que saben que son incorrectas,
- $\color{orange}{\text{orange}}$ dígitos son los que tienen un solo dígito correcto entre ellos,
- $\color{blue}{\text{blue}}$ dígitos son los que tienen sólo un dígito incorrecto, entre ellos,
- negro dígitos significa que no tenemos ninguna información sobre ellos.
Observe que si podemos escribir un dígito en verde también podemos escribir en rojo (utilizando el valor opuesto), es básicamente el conocimiento equivalente. Del mismo modo, el naranja y el azul son equivalentes (se puede ir de uno a otro moviendo los valores de los dígitos).
Voy a utilizar estos colores para describir las deducciones que podemos hacer después de una respuesta (incluyendo el conocimiento de las anteriores respuestas). Al escribir las suposiciones que sólo voy a utilizar el color verde para indicar que no debemos preocuparnos por estos dígitos, ya hemos encontrado (el resto de la estimación se hará por escrito en negro, aunque podamos tener información sobre estos dígitos). Por último, voy a indicar los bits cambiado desde el anterior supongo que con rayas discontinuas superiores. Por ejemplo, si mi primera conjetura es $111100000$ y para el segundo supongo que intercambiar la primera y la última bits, voy a escribir: $\overline0 1110000 \overline1$. Esto hace que sea más fácil seguir los movimientos/conjeturas.
Así que vamos a empezar con la suposición de que produce una respuesta de $1$ y ver lo que podemos deducir. Recuerde que nuestro objetivo desconocido es $001111000$
Guess1 $100000111$, reply $1$, $\implies \color{red}1 \color{orange}{00000} \color{red}{111} $
Como se discutió antes, sabemos que todos nuestros 1s son incorrectos. También si sabemos $\color{red}1 \color{orange}{00000} \color{red}{111}$ equivalente saber $\color{green}0 \color{blue}{11111} \color{green}{000}$. Esto significa que sólo tenemos que encontrar a la única 0 en los cinco números azules tenemos.
Guess2 $\overline{\color{green}0 1111}0\overline{ \color{green}{000}}$, reply $7$, $\implies \color{green}0 \color{blue}{1111}\color{red}0 \color{green}{000}$
Guess3 $\color{green}0 111\overline 0\color{green}{\overline1 000}$, reply $7$, $\implies \color{green}0 \color{blue}{111}\color{red}0 \color{green}{1000}$
Guess4 $\color{green}0 11\overline0 \color{green}{\overline1 1000}$, reply $7$, $\implies \color{green}0 \color{blue}{11}\color{red}0 \color{green}{11000}$
Guess5 $\color{green}0 1\overline0 \color{green}{\overline1 11000}$, reply $7$, $\implies \color{green}0 \color{red}{10} \color{green}{111000}$
Guess6 $\color{green}{0\overline{01}111000}$, reply $9$, Éxito
Así que, esencialmente, se encontraron cuatro de los cinco ceros después de nuestra primera conjetura y, a continuación, tratamos de encontrar el resto de cero entre 5 dígitos (lo que puede tardar hasta más de 5 intentos en el peor de los casos)
Primero supongo que devuelve 7 bits correctos
Vamos a ver ahora cómo íbamos a reaccionar cuando nuestra primera conjetura devuelve una respuesta de 7.
Guess1 $000111100$, reply $7$, $\implies \color{blue}{000111100}$ (2 los dígitos son incorrectos, pero no quiero utilizar otro color, para evitar una sobrecarga)
Así que sabemos que tenemos que encontrar el par correcto para intercambiar. Pero hay 20 posibles pares (cada uno de los cuatro 1s puede ser intercambiado con cada uno de los 5 0s). ¿Cómo podemos encontrar la correcta en 5 conjeturas? Iniciar el intercambio y recopilar información.
Guess2 $\overline1 00 \overline0 11100$, reply $5$, $\implies \color{red}1 \color{blue}{00} \color{red}0 \color{blue}{11100}$ (azul: 2 dígitos son incorrectos)
Guess3 $\color{green}0\overline1 0\color{green}1 \overline0 1100$, reply $5$, $\implies \color{green}0 \color{red}1 \color{blue}{0} \color{green}1 \color{red}0 \color{blue}{1100}$ (azul: 2 dígitos son incorrectos)
Guess4 $\color{green}{00} \overline1 \color{green}{11} \overline0 100$, reply $7$, $\implies \color{green}{00} \color{orange}1 \color{green}{11} \color{orange}0 \color{blue}{100}$ (azul: 1 dígito es incorrecto)
Sabemos que estos dos dígitos son de color naranja (así es la correcta y una incorrecta) porque son los únicos cambios con respecto a Guess1, y la respuesta aún es $7$. Así que ahora debemos seleccionar el intercambio de nuevo uno de ellos con un dígito, y ver cuál es el resultado. Si tenemos suerte y conseguimos $9$ partidos de terminar. O la podemos obtener a $5$ partidos y sabemos que estas dos dígitos incorrectamente se intercambia lo que significa que sabemos que es el correcto y que el número incorrecto de la swap anterior. Por último, podemos obtener $7$ partidos de nuevo, lo que significaría que otra vez podemos averiguar la correcta y la incorrecta dígitos de la swap anterior. Vamos a tratar el peor de los casos aquí:
Guess5 $\color{green}{00} \overline0 \color{green}{11} 01 \overline1 0$, reply $5$, $\implies \color{green}{00} \color{red}0 \color{green}{11} \color{red}0 \color{blue}1 \color{red}1 \color{blue}0$ (azul: 1 dígito es incorrecto)
Porque sabemos que hay sólo 4 1s sabemos la respuesta para el blues: ambos son 0.
Guess6 $\color{green}{00 \overline1 11\overline{100}0}$, reply $9$, Éxito
Primero supongo que devuelve 5 bits correctos
Vamos a comenzar a examinar el caso cuando nos encontramos con 5 partidos con nuestra primera conjetura. Voy a empezar, pero no la conclusión de que, como la respuesta se vuelve tedioso. Yo se lo dejo como ejercicio para el OP. Lo mismo ocurre para el caso cuando nos encontramos con 3 partidos con nuestra primera conjetura.
Guess1 $100011100$, reply $5$, $\implies \color{blue}{100011100}$ (4 los dígitos incorrectos)
De nuevo tenemos que empezar por el intercambio de dos bits aleatorios (que tienen diferentes valores). Si nuestra respuesta es $7$, entonces estamos en la misma subcase como se examinó anteriormente: a sabiendas de 2 dígitos, y el que tiene 2 errores en el resto. Si la respuesta es$3$, entonces estamos en el subcase donde sabemos que 2 dígitos y hay 4 errores en los 7 restantes ( procedemos del mismo modo con los 7 restantes dígitos). El más desafiante subcase aquí es que hacemos un intercambio, y volvemos a obtener una respuesta de $5$. Esto significa que sólo un dígito incorrecto fue canjeado. Por ejemplo:
Guess2 $\overline{01}0011100$, reply $5$, $\implies \color{orange}{01}\color{blue}{0011100}$ (azul: 3 dígitos son incorrectos)
Así que ahora tenemos que elegir uno de estos bits y cambiamos de nuevo, con otro poco.
Guess3 $0\overline{01}011100$, reply $7$, $\implies \color{green}{001}\color{blue}{011100}$ (azul: 2 dígitos son incorrectos)
Os dejo el resto de los movimientos como un ejercicio.
Otras estrategias
Pensé un poco acerca de cómo solucionar el problema cuando dicen que sólo tenemos una 1 bits en el 9-cadena de bits. Al principio pensé que necesitábamos 9 conjeturas en el peor de los casos. Pero esto sólo ocurre si nos atenemos a la restricción de que nuestras conjeturas tener el número correcto de 1 bits en ellos. Cuando sólo tenemos un 1 bits es mejor dejar ir de esta restricción, en lugar de hacer una especie de búsqueda binaria en la cadena, por establecer inicialmente la mitad de los bits a 1 (redondeado al entero más cercano) y ver cómo muchos de los errores que conseguir. Esto nos permitirá saber si el 1 bit es la en la que elegimos, o no. Procedemos de esta manera y en la mayoría de los 5 conjeturas tenemos nuestra respuesta.
Me pregunto si el profesor proporciona una fórmula general para la máxima conjeturas es necesaria cuando se $r$ 1 bits en un $n$-cadena de bits.
