Problema lógico: Identificar los vinos envenenados de una muestra, minimizando los sujetos de prueba con restricciones

Question

Acabo de salir de mi clase de Matemáticas y Lógica con mi amigo. Durante la clase, se presentó un conocido rompecabezas matemático/lógico:

El Rey ha $1000$ vinos, $1$ del cual está envenenado. Necesita identificar el vino envenenado lo antes posible y con los menores recursos, por lo que contrata al protagonista, un matemático. El rey le ofrece sus sirvientes prescindibles para que le ayuden a comprobar qué vino está envenenado.

El vino envenenado es muy potente, tanto que una sola molécula del vino provocará la muerte de cualquiera que lo beba. Sin embargo, es de acción lenta. La naturaleza del veneno de acción lenta significa que sólo hay tiempo para probar un "trago" por sirviente. (Una bebida puede ser una mezcla de cualquier número de vinos) (Supongamos que el Rey necesita saberlo en una hora, y que cualquier veneno en la bebida tarda una hora en mostrar cualquier síntoma)

¿Cuál es la cantidad mínima de sirvientes que necesitaría para identificar el vino envenenado?

Con suficiente tiempo y razonamiento, uno puede ver eventualmente que esto requiere como máximo diez ( $10$ ) sirvientes (de hecho, se podrían probar 24 vinos más además de esos 1000 antes de necesitar un undécimo sirviente). La prueba/procedimiento se deja al lector.

Sin embargo, mi amigo y yo no nos conformamos con esta respuesta. Mi amigo añadió la pregunta:

¿Qué sería diferente si hubiera $2$ ¿vinos que fueron envenenados de los 1000? ¿Cuál es entonces el nuevo mínimo?

Al final generalizamos el problema a esto:

Dado $N$ botellas de vino ( $N \gt 1$ ) y, de esos, $k$ vinos envenenados ( $0 \lt k \lt N$ ), cuál es el método óptimo para identificar todos los vinos envenenados, y cuántos servidores se necesitan ( $s(N,k)$ )?

Después de hacer algunos cálculos, mi amigo y yo conseguimos encontrar algunos límites inferiores y superiores (posiblemente poco útiles):

$log_2 {N \choose k} \le s(N,k) \le N-1$

Esto se debe a que $log_2 {N \choose k}$ es el número mínimo de servidores para identificar de forma única el $N \choose k$ posibles configuraciones de $k$ vinos envenenados en $N$ total de vinos.

¿Puede alguien ayudarnos a encontrar una estrategia óptima? Además de la trivial que requiere $N-1$ servidores. ¿Qué tal un posible enfoque para empezar?

¿Sería este problema diferente si sólo se requiriera encontrar una estrategia que con seguridad encontrara un vino que sea no envenenado, en lugar de identificar todos los vinos envenenados? (aparte de la solución ligeramente trivial de $k$ servidores)

Answer 1

Hice esta pregunta en MathOverflow y obtuve una gran respuesta allí.

---

Para $k = 2$ Puedo hacerlo con ${\lceil \log_2 N \rceil + 2 \choose 2} - 1$ sirvientes. En particular para $N = 1000$ Puedo hacerlo con $65$ servidores. La prueba es algo larga, así que no quiero publicarla hasta que haya pensado más en el problema.

---

No he podido mejorar el resultado anterior. Así es como funciona. Dejemos que $n = \lceil \log_2 N \rceil$ . Permítanme repasar el algoritmo para $k = 1$ para que todos estemos en la misma página. Numera los vinos y asigna a cada uno de ellos la expansión binaria de su número, que consiste en $n$ bits. Encuentre $n$ siervos, y tienen siervos $i$ beber todos los vinos cuyo $i^{th}$ bit es $1$ . Entonces el conjunto de sirvientes que mueren te dice la expansión binaria del vino envenenado.

Para $k = 2$ necesitamos encontrar $n$ mayordomos, $n$ criadas, y ${n \choose 2}$ cocineros. Los cocineros se llamarán $(i, j)$ para algunos enteros positivos $1 \le i < j \le n$ . Tener mayordomo $i$ beber todos los vinos cuyo $i^{th}$ bit es $1$ , tener una criada $i$ beber todos los vinos cuyo $i^{th}$ bit es $0$ , y tener un cocinero $(i, j)$ beber todos los vinos tales que la suma de los $i^{th}$ a través de la $j^{th}$ bit, inclusive, mod 2, es $1$ . Así es como se desglosa el trabajo de los mayordomos y camareras.

• Si ambos mayordomos $i$ y la criada $i$ morir, entonces uno de los vinos envenenados tiene $i^{th}$ bit $0$ y el otro tiene $i^{th}$ bit $1$ .
• Si sólo el mayordomo $i$ muere, entonces los dos vinos envenenados tienen $i^{th}$ bit $1$ .
• Si sólo la criada $i$ muere, entonces los dos vinos envenenados tienen $i^{th}$ bit $0$ .

Los dos segundos casos son geniales. El problema con el caso 1 es que si ocurre más de una vez, sigue habiendo ambigüedad sobre qué vino tiene cada bit. (El peor escenario es si todos los mayordomos y criadas mueren.) Para solucionar el problema del caso 1, utilizamos a los cocineros.

Dejemos que $i_1 < ... < i_m$ sea el conjunto de bits en los que se da el caso 1. Diremos que el vino envenenado cuyo $(i_1)^{th}$ bit es $1$ es el vino A, y el otro es el vino B. Obsérvese que la suma de los $(i_1)^{th}$ a través de $(i_2)^{th}$ bits del vino A mod 2 es igual a la suma de los $(i_1)^{th}$ a través de $(i_2)^{th}$ bits de vino B mod 2, y podemos determinar cuál es esta suma mirando si cook $(i_1, i_2)$ murió. El valor de esta suma determina si el $(i_2)^{th}$ bit del vino A es 1 o 0 (y lo mismo para el vino B). Del mismo modo, si se observa si el cocinero $(i_j, i_{j+1})$ murió nos dice los trozos restantes del vino A, por lo tanto del vino B.

---

Un último comentario por ahora. El límite inferior no es posible cuando $k$ es grande en comparación con $N$ por ejemplo, cuando $k = N-1$ se necesita $N-1$ servidores. La razón es que cualquier sirviente que beba más de un vino muere automáticamente, por lo que no te da ninguna información.

Answer 2

Solución con 42 sirvientes (también 41):

Esto da una solución, para 2 venenos, usando 42 sirvientes, para 2187 (=3^7) vinos. Representar los vinos utilizando el sistema numérico trinario. Obtendrás 7 Trits. Tenemos que averiguar los trits de los dos venenos.

    A-B-C-D-E-F-G

(A) Para el Trit A, dar vinos con valores 0,1,2 a 3 personas únicas respectivamente. Haz pruebas similares para el resto de los Trits. Habrá 7*3=21 pruebas de este tipo.

(B) Mezcla de vinos con valores AB {00,11,22}. Entrégalo a una única persona. Haz pruebas similares con todas las 2 combinaciones de Trits. Habrá C(7,2)=21 pruebas de este tipo.

En el Paso (A), para un Trit dado, como máximo, morirán 2 personas. Si sólo muere una persona muere, ese Trit se resuelve. Digamos que algunas Trits (B,C,E) no se han resuelto.

    1-(0|1)-(1|2)-0-(1|2)-0-0

Para vincular B&C, compruebe si la persona para BC ha fallecido en el paso(2). Si es así, BC son {02,11}; si no, {01,12}.
Para vincular C&E, compruebe si la persona para CE ha fallecido en el paso(2). Si es así, CE son {11,22}; si no, {12,21}.

Número total de pruebas = 21+21 = 42

---

Explicación:

La idea es que, al comparar los Trits (en el Paso B), sólo tenemos que considerar dos grandes categorías. Una con un solo valor común. Una con dos valores comunes (no tener un valor común es imposible). Supongamos que los trits A&D no se resolvieron.

Follg muestra que sólo tienen un valor común ( 0 )

    A   D
    =====
    0   0
    1   []
    []  2

Follg muestra que tienen dos valores comunes ( 0 , 1 ).

    A   D
    =====
    0   0
    1   1
    []  []

En cualquier caso, para relacionarlos, basta con saber si al menos uno de {00,11,22} ha muerto. Eso resuelve los valores de los dos trits.

---

Nota: Una solución para 1458 vinos, 2 venenos, puede ser formulada con 41 servidores utilizando 7 dígitos ( 6 Trits + 1 Bit ). Este truco no tiene mucho valor; podría encontrar su uso en la prueba de un mayor número de venenos.

Answer 3

Solución con 40 sirvientes:

Representa los vinos utilizando el sistema numérico de base 4. Obtendrás 5 dígitos (para 4^5=1024 vinos)

    A-B-C-D-E

(A) Para el dígito A, dar vinos con valores 0,1,2,3 a cuatro personas únicas respectivamente. Haz pruebas similares para el resto de los dígitos. Habrá 5*4=20 pruebas de este tipo.

(B) Mezcla de vinos con valores AB {00,11,22,33}. Entrégalo a una sola persona. Haz pruebas similares con todas las combinaciones de 2 dígitos. Habrá C(5,2)=10 pruebas de este tipo (gráfico azul).

(C) Mezcla de vinos con valores AB {10,21,32,03}. Entrégalo a una sola persona. Haz pruebas similares con todas las combinaciones de 2 dígitos. Habrá C(5,2)=10 pruebas de este tipo (gráfico verde).

En el paso (A), para un dígito dado, como máximo, morirán 2 personas. Si sólo muere una persona, ese dígito se resuelve. Si mueren 2 personas, significa que tiene dos valores (uno para cada veneno).

Digamos que dos dígitos D&E tienen dos valores cada uno. Para enlazarlos, hay que mirar si la persona del Paso(B) y del Paso(C) murió por D&E. Eso es suficiente para enlazar los dígitos.

Explicación:

Mira los dos gráficos.

Supongamos que D tiene valores (1,3). Juntos, conectan con 0,1,2,3 (todos los valores posibles de E). Este es el mejor caso. No importa qué dos valores de E elijas, puedes conectarlos de forma única con los valores de D.

Supongamos que D tiene valores (1,2). Juntos, conectan con 0,1,2. Un valor de E (=3) queda sin conectar. Este es el peor caso. Aun así, no importa qué dos valores de E se seleccionen, al menos uno de ellos permanece conectado con los valores de D. Eso es suficiente para nosotros.

Answer 4

Esto da una solución usando 60 servidores para 1024 vinos.Representar los vinos usando números binarios de 10 bits. Nombra los bits de la A a la J. Agrupa los bits adyacentes.

    AB--CD--EF--GH--IJ

¿Cuál es el valor de AB para los venenos? Da los siguientes conjuntos de vinos a 4 personas diferentes.

    AB=00; AB=01; AB=10; AB=11

Si sólo uno de ellos muere, el AB está completamente resuelto. Si no, obtenemos información parcial. Haz pruebas similares en los 4 grupos restantes.

    00--0(0|1)--11--(0|1)1--1(0|1)

Considere la posibilidad de CD y GH. Si sabemos que el conjunto DG=00 murió, podemos enlazarlos. Como no sabemos qué prueba sería necesaria, ejecutamos las 4 pruebas:

    CG=00; CH=00; DG=00; DH=00

Lo mismo ocurre con GH y JK. Si GJ=00 no murió, los venenos serán:

    00--00--11--01--11
    00--01--11--11--10

Número total de pruebas/personas necesarias: 5*4 + C(5,2)*4 = 60

---

P.D.: Si utilizas grupos de 3 (en lugar de 2), no mejora. Si usas grupos de 4 o más, empeora.

Answer 5

Hay dos soluciones: la binaria y la dimensional.

La solución binaria:

Damos a cada botella un número binario correspondiente a su posición numérica en la línea de botellas. Necesitamos suficientes columnas para acomodar el número de botellas dado. Por ejemplo, si tenemos 8 botellas :

0 -> 000

1 -> 001

2 -> 010

3 -> 011

4 -> 100

5 -> 101

6 -> 110

7 -> 111

(Nota: la primera botella tiene la posición 0)

Podemos probar con tres columnas. Se hacen tres dosis, una por cada columna, tomando una gota de cada botella si y sólo si tiene un 1 en esa columna. Por ejemplo, la primera muestra tiene gotas de las botellas 4,5,6 y 7.

Cada dosis se administra a una persona. Sólo anotamos cuál de ellas muere. Si no muere ninguna, la primera botella tiene veneno. Si mueren todos, la octava botella (número 7, binario) está envenenada. Si mueren el primero y el tercero, la sexta botella (número 5, binario).

La solución binaria da lugar a un número incierto de muertes, con una media de 1,5, es decir, el 50%. Pero utiliza el menor número de catadores.

La solución dimensional:

En el caso más sencillo, tratando las botellas como puntos de una línea, necesitamos 1000 sirvientes y 1 troquel.

Para hacer un cuadrado, necesitamos 32 filas y 32 columnas. Algunos espacios están vacíos, no importará, ya que los espacios vacíos tienen el mismo efecto que las botellas no envenenadas.

Cada dosis tiene gotas de 1 fila. 64 personas toman la dosis, dos mueren, indicando una fila y una columna, la botella de veneno está en la intersección.

Haciendo un cubo, tenemos 10 x 10 x 10 botellas. Hacemos 3 dosis con una gota de cada cuadrado, en los ejes x y z. De nuevo, la botella envenenada está en la intersección.

La progresión debería estar ahora clara:

Disposición: Línea

Consta de: Puntos

Prueba con : Puntos

Número utilizado: 1000

Número de muertos: 1

Arreglo: Cuadrado

Consta de: Líneas

Prueba con : Líneas

Número utilizado: 32 x 2 = 64

Número de muertos: 2

Arreglo: Cubo

Consta de: Cuadros

Prueba con : Cuadros

Número utilizado: 10 x 3 = 30

Número de muertos: 3

Para cualquier número de botellas, para ordenarlas en n dimensiones tomamos la raíz n y redondeamos al siguiente número entero superior. En 5 dimensiones, utilizamos 20 probadores y 5 dados.

Las dimensiones pueden seguir aumentando.