Pocas veces un problema tan corto abre una idea tan grande. Aquí no gana quien prueba más, sino quien saca el máximo partido de lo que cada rata puede decir.
Las mil botellas envenenadas
Enunciado
Tienes 1000 botellas de vino. Una de ellas está envenenada, y una sola gota basta para matar a una rata exactamente 24 horas después.
Dispones de 10 ratas de laboratorio y solo puedes hacer una ronda de pruebas. Puedes preparar para cada rata una mezcla con gotas de varias botellas.
¿Cómo identificas con certeza la botella envenenada en un único ciclo de 24 horas?
Ver solución
Solución
Respuesta: usa las 10 ratas como los 10 bits de un código binario.
Numera las botellas del 0 al 999. Cada número puede escribirse en binario con 10 bits, porque:
Asigna cada rata a una de esas 10 posiciones binarias. Para cada botella, mira su número en binario: si en una posición hay un 1, das una gota de esa botella a la rata correspondiente; si hay un 0, esa rata no prueba esa botella.
Por ejemplo, la botella 13 se escribe en binario con 10 bits como:
Eso significa que esa botella se incluye en la mezcla de las ratas correspondientes a los tres 1 de ese código. Si numeramos las posiciones de derecha a izquierda, morirían las ratas 1, 3 y 4.
Tras 24 horas, cada rata muerta marca un 1 y cada rata viva marca un 0. El patrón completo de muertes forma un número binario de 10 bits.
Si el patrón observado fuera:
leeríamos ese número en binario y obtendríamos 13. Por tanto, la botella envenenada sería la número 13.
Como 10 bits permiten distinguir 1024 patrones distintos, son suficientes para identificar con certeza una botella entre 1000.