Conejos bebe botellas de agua envenenada (problema de combinatoria)

Question

Supongamos que tenemos $n$ botellas de agua, uno de los cuales es envenenado y que queremos identificar. Una mezcla puede ser formado por la mezcla de un cierto número de botellas de agua. Tenemos $k$ conejos, y cada día, cada uno de los conejos se puede dar una mezcla de un conejo muere si la mezcla contiene veneno. ¿Cuántos días son necesarios para determinar la botella está envenenado?

Una similar, pero ligeramente diferentes del problema, que se discute aquí: problema de Lógica: la Identificación de los envenenado vinos de una muestra, minimizando los sujetos de prueba con restricciones

Answer 1

Deje que la respuesta se $S(n, k)$. Todos fraccionaria del número de días que deben redondear (soy vago para escribir el techo de la función.

Si $k=1$, entonces sólo podemos hacer la prueba 1 vino cada día, así que tenemos $n-1$ días. Recuerde que si sólo hay 1 vino de la izquierda, debe ser envenenado. Por lo $S(n, 1) = n-1$.

Si $k=2$, luego dividiendo el vino en 3 grupos de $ \alpha, \beta, n-\alpha - \beta$ en el primer día, y las pruebas de los 2 primeros grupos en contra de los 2 conejos. Si ambos sobreviven, el veneno está en el último grupo, y se llevará a $S(n - \alpha - \beta, 2) + 1$ días. De lo contrario, el veneno está en los primeros 2 grupos y se llevará a $S(\alpha, 1) + 1$ o $S(\beta, 1) + 1$ días. Por lo tanto, con el fin de minimizar el número de días, queremos establecer estos valores a ser las mismas. Esto nos da $S(\alpha, 1) + 1 = \alpha - 1 + 1 = \alpha$, lo $\alpha = \beta = S(n - 2\alpha, 1)+1$.

Desde $S(1, 2) = 0$$S(2, 2) = 1$, así que si tenemos $\alpha = \beta = 1$,$n - 2\alpha \leq 1$. Esto demuestra que $ S(2, 2)=1, S(3, 2) = 1$ dando 1 conejo de 1 vino cada uno y que $(4, 2) =2$.

Desde $S(3, 2)=1$$(4, 2) =2$., así que si tenemos $\alpha = \beta = 2$,$n - 2\alpha \leq 3$. Esto demuestra que $S(4, 2) = 2, S(5, 2) = 2, S(6, 2) = 2, S(7, 2) = 2$ dando 1 conejo 2 vinos de cada uno, y que $S(8, 2) = 3$.

El patrón de la de mayor valor de $n$ tal que $S(n, 2) = m-1$$1, 3, 7, 13, \ldots$, donde estamos añadiendo $2m$ a cada término, por lo que los términos de la serie es $1+(m-1)\times m$. Por lo tanto, si $1 + (m-2) \times (m-1) < n < 1 + (m-1)\times m$,$S(n, 2) = m$.

Usted puede seguir este procedimiento con $k=3$ conejos. Romper los vinos en 4 grupos de $\alpha, \beta, \gamma, n-\alpha -\beta - \gamma$, y lo de la prueba de los 3 primeros grupos en los 3 conejos. Queremos $\alpha = \beta = \gamma = S(n- \alpha - \beta - \gamma, 2)$. A continuación, $S(n,3) = 1 + \alpha$.

Lamentablemente, no estoy seguro de cómo generalizar esta.

Answer 2

En $d$ días de prueba, cada conejo puede experimentar en la mayoría de los $(d+1)$ resultados: en vivo para todos los $d$ días, o a morir en algún día de$1$$d$. Con $k$ conejos, entonces, el número de posibles resultados en $d$ días es en la mayoría de las $(d+1)^{k}$. El número máximo de botellas de las que una sola botella de veneno pueden ser identificados también debe satisfacer $$ N(k,d) \le (d+1)^{k}.$$ Vamos a mostrar que este obligado es apretado, por lo $N(k,d)=(d+1)^k$ exactamente. Esto es claramente cierto para $d=0$. La prueba de $d\ge 1$ es inductivo en $d$. Supongamos que hemos demostrado que $N(m,d-1)=d^{m}$ todos los $m$. Dado $(d+1)^k$ botellas y $k$ conejos, procedemos de la siguiente manera. Para cada bitstring de longitud $k$ que contiene $m$ $0$'s, label $d^m$ botellas con que bitstring. El número total de botellas etiquetadas es $$ \sum_{m=0}^{k}{{k}\, seleccione{m}}d^m=\sum_{m=0}^{k}{{k}\, seleccione{m}}d^m1^{k-m}=(d+1)^k. $$ Ahora una mezcla de la alimentación a cada conejo, $i$, que incluye el agua de la botella con un $1$ $i$- ésimo lugar de su bitstring. Al final del día, el bitstring con $1$'s en los lugares correspondientes a los muertos conejos será exactamente la etiqueta de la botella envenenada. Si $k-m$ conejos han muerto (que será el caso para algunos $0\le m\le k$), el seleccionado bitstring ha $k-m$ $1$'s y $m$ $0$'s; hay $d^m$ botellas con que bitstring, y tenemos $m$ sobreviven a los conejos y a $d-1$ días que quedan para identificar el veneno de la botella de en medio de ellos. Por la hipótesis inductiva, esto es suficiente, lo que completa la prueba.

Así, con $k$ conejos y $d$ de los días, el número máximo de distinguible de las botellas es exactamente $(d+1)^k$. La inversión de este, vemos que para el caso de la $n$ botellas y $k$ conejos, necesitamos estar permitido $$ D(n,k)=\left\lceil n^{1/k}-1 \right\rceil $$ días para encontrar el veneno.