acertijo del día

Dieciséis posibilidades y una respuesta que podría ser falsa. Tus preguntas deben quedar fijadas antes de empezar.

Dieciséis números y una mentira

Genio
Lógica pura

Enunciado

Pienso un número entero entre 1 y 16.

Puedes formular cualquier pregunta cuya respuesta sea sí o no, con una condición: debes dejar preparadas todas las preguntas antes de recibir la primera respuesta. No podrás cambiarlas después.

Responderé a todas, pero durante la conversación puedo mentir como máximo una vez. También es posible que no mienta nunca.

¿Cuál es el menor número de preguntas que garantiza que descubras el número?

Ver solución

Solución

Respuesta: hacen falta exactamente 7 preguntas.

Por qué seis no bastan

Supongamos que hacemos \(q\) preguntas. A cada número le corresponde una secuencia de \(q\) respuestas verdaderas.

Como puede haber una mentira, ese número puede producir \(q+1\) secuencias distintas:

  • la secuencia verdadera;
  • una por cada posible respuesta alterada.

Las secuencias correspondientes a números diferentes no pueden coincidir, pues entonces no sabríamos cuál fue elegido.

Con seis preguntas necesitaríamos

$ 16(6+1)=112 $

secuencias distintas, pero solo existen

$ 2^6=64. $

Por tanto, seis preguntas —y, en consecuencia, cualquier cantidad menor— son insuficientes.

Cómo hacerlo con siete

Escribe el número elegido menos uno en binario mediante cuatro bits:

$ n-1=abcd, $

donde \(a\) es el bit de mayor valor.

Usaremos el símbolo \(\oplus\) para la suma módulo 2: vale 1 cuando hay un número impar de unos.

Preparamos estas siete respuestas verdaderas:

$ \begin{aligned} c_1&=a\oplus b\oplus d, & c_2&=a\oplus c\oplus d, & c_3&=a,\\ c_4&=b\oplus c\oplus d, & c_5&=b, & c_6&=c, & c_7&=d. \end{aligned} $

La pregunta \(i\) es simplemente:

¿Es \(c_i=1\)?

Recibimos las respuestas \(r_1,\ldots,r_7\). Para comprobarlas calculamos:

$ \begin{aligned} s_1&=r_1\oplus r_3\oplus r_5\oplus r_7,\\ s_2&=r_2\oplus r_3\oplus r_6\oplus r_7,\\ s_3&=r_4\oplus r_5\oplus r_6\oplus r_7. \end{aligned} $

Si nadie mintió, las tres paridades valen cero.

Si una respuesta fue falsa, el número

$ j=s_1+2s_2+4s_3 $

indica exactamente su posición entre 1 y 7. Corregimos \(r_j\) y recuperamos los cuatro bits:

$ a=r_3,\qquad b=r_5,\qquad c=r_6,\qquad d=r_7. $

Estos cuatro bits determinan \(n-1\), y por tanto el número elegido.

Así, siete preguntas bastan y seis no:

$ \boxed{7}. $

El ajuste es perfecto:

$ 16(7+1)=128=2^7. $

Cada uno de los 16 números ocupa exactamente ocho secuencias posibles: la verdadera y las siete que contienen una mentira.

Idea esencial: las tres paridades no solo detectan que existe una respuesta falsa; indican cuál es, para poder corregirla.