Identificando vinos envenenados

Question

La versión estándar de este rompecabezas es la siguiente: usted tiene $1000$ botellas de vino, uno de los cuales está envenenado. Usted también tiene un suministro de ratas (dicen). Desea determinar que la botella es el envenenado uno por la alimentación de los vinos a las ratas. El vino envenenado tarda exactamente una hora para trabajar y es indetectable antes de entonces. Cuántas ratas son necesarios para encontrar la botella envenenada en una hora?

No es difícil ver que la respuesta es $10$. Camino de regreso cuando matemáticas.SE inicia por primera vez, una generalización se considera el lugar donde más de una botella de vino envenenado. La estrategia que funciona para la versión estándar no funciona para esta versión, y sólo pude encontrar una solución para el caso de $2$ envenenado botellas que requiere de $65$ ratas. Asintóticamente mi solución requiere de $O(\log^2 N)$ ratas para detectar $2$ envenenado botellas de $N$ botellas.

Nadie puede hacerlo mejor asintóticamente y/o demostrar que su respuesta es óptima y/o encontrar una solución que funcione para más envenenada botellas? El número de envenenado botellas, supongo, debe ser mantenido constante, mientras que el número total de botellas está permitido convertirse en grande para asintótico de las estimaciones.

Answer 1

Cada botella de vino corresponde al conjunto de las ratas que probado. Deje $\mathcal{F}$ ser parte de la familia de los conjuntos resultantes. Si las botellas correspondientes a los conjuntos de $A$ e $B$ son envenenados, a continuación, $A \cup B$ es el conjunto de ratas muertas. Por lo tanto, podemos identificar los envenenados botellas como de largo como para todos los $A,B,C,D \in \mathcal{F}$ tal que $A \cup B = C \cup D$ tenemos $\{ A, B \} = \{ C, D \}$. Las familias con esta propiedad se llama (fuertemente) unión libre y el máximo tamaño posible de $f(n) $ de una unión libre de la familia $\mathcal{F} \subset 2^{ [n] } $ ha sido estudiado en extremal combinatoria. En la cuestión de contexto, $f(n)$ es el número máximo de botellas de vino que puede ser probado por $n$ ratas.

En el periódico "la Unión libre de Hypergraphs y la Teoría de la Probabilidad" Frankl y Furedi muestran que $$2^{(n-3)/4} \leq f(n) \leq 2^{(n+1)/2}.$$ La prueba de que el límite inferior es algebraica, constructiva, y, creo, muy elegante. En particular, uno puede encontrar la $2$ envenenado botellas de $1000$ con $43$ ratas.

Answer 2

Este problema también se conoce con el nombre de "no adaptativa de la combinatoria del grupo de pruebas" y ha existido por lo menos desde la segunda Guerra Mundial, cuando el gobierno de Estados Unidos estaba tratando de aislar los casos de sífilis en los soldados. ("No adaptativa" significa que usted tiene que especificar todas las pruebas de antelación, mientras que la "adaptación" significa que usted puede utilizar los resultados de las pruebas antes de decidir que hacer a continuación.)

El estándar de referencia en pruebas en grupo parece ser la Combinatoria del Grupo de Prueba y Sus Aplicaciones, por Du y Hwang. La parte II, que comprende los Capítulos 7-9, es en no adaptativa de la prueba. En particular, la búsqueda de la óptima pruebas de estructuras cuando hay dos o más "defectos" es todavía un problema abierto.

Sin embargo, si $t(d,n)$ es el número de pruebas necesarias para aislar $d$ defectos de $n$ total de sujetos, de los límites $\Omega(\frac{d^2}{\log d} \log n) \leq t(d,n) \leq O(d^2 \log n)$ son conocidos. El artículo de la Wikipedia sobre la disparidad de las matrices tiene una discusión y algunas pruebas.

---

Puede ser interesante comparar la solución para la adaptación de la versión de este problema, como podemos dar una respuesta definitiva en este caso.

Deje $n(t)$ indicar el número máximo de botellas de vino para que 2 envenenado pueden ser identificados en $t$ tests adaptativos. En el "Grupo de prueba con dos y tres defectos" (Anales de la New York Academy of Sciences 576, pp 86-96, 1989) Chang, Hwang, y Weng dar explícita de los procedimientos de prueba de que el rendimiento de los límites inferiores $$n(t) \geq 89 \cdot 2^{\frac{t}{2}-6}, t \text{ even, } t \geq 12;$$ $$n(t) \geq 63 \cdot 2^{\frac{t-1}{2}-5}, t \text{ odd, } t \geq 13.$$

En el Du y Hwang texto se muestra que, para $t \geq 4$, tenemos que el límite superior $$n(t) \leq 2^{\frac{t+1}{2}} - 1/2.$$
(Tenga en cuenta que este es el límite superior de $f(n)$ dado en Sergey Norin la respuesta.)

Estos límites nos dicen que $n(18) \leq 723$ pero $n(19) \geq 1008$. Por lo tanto 2 envenenado botellas pueden ser identificados de 1000 en 19 de tests adaptativos, pero no menos, mediante el procedimiento de prueba descrito en el Chang, Hwang, y Weng de papel.

Answer 3

Usted se dará la solución en el enlace: el método de probabilidades. Sin tratar de optimizar, tome $r$ ratas y para cada uno elegir el subconjunto de vinos al azar, cada vino con una probabilidad de $1/2$ (por ejemplo). Llamar a estos subconjuntos $A_m$. Ahora vamos a $\{i,j\}$ e $\{k,l\}$ dos posibilidades para que las botellas están envenenados. Queremos saber si hay una rata en la separación de estas dos posibilidades, es decir, que el resultado si el $i$-th y $j$-th botellas son los envenenados uno será diferente para que la rata, entonces, si la $k$-th y $l$-th botellas están envenenados. Para cualquier específicos de la rata, esto sucede si $A_m$ intersecta $\{i,j\}$ pero no $\{k,l\}$, o viceversa. Esto sucede con algunos fijos probabilidad positiva (de nuevo, no de la optimización). Por lo tanto, se produce un error con una probabilidad de $q$ que es estrictamente menor que 1. Por lo tanto, la probabilidad de que se produzca un error para todos los $\{A_m\}_{m=1}^r$ es $q^r$. Hay menos de $n^4$ pares de posibilidades para envenenado botellas de vino, por lo tanto la probabilidad de tener un par para que esta falla es en la mayoría de las $n^4 q^r$ y teniendo en $r=C \log n$ es suficiente para hacer que este insignificante.

Answer 4

Hay un problema similar en comprimido de detección genética de detección de alelos raros (cf http://nar.oxfordjournals.org/content/38/19/e179.full ). La técnica funciona casi aquí podemos determinar cuánto veneno de rata consigue. Parece razonable, una rata que hace más veneno muere más rápido.

En nuestro problema la idea sería crear un ejemplo para cada rata para beber por azar la agrupación de juntas de vino de muchas botellas. Específicamente, para la rata $i$ dibujamos $A_{ij}$ litros de vino de cada una de las $j=1,...,N$ botellas de donde $A_{ij}$ es $\mathcal{N}(0,1)$ distribuido. Deje $b_i$ denotar la cantidad de veneno medido en la rata $i$ y deje $x_j$ denotar la cantidad de veneno en la botella de $j$.

Esto produce que el altamente indeterminado sistema lineal $$ Un\vec{x} = \vec{b} $$ donde sabemos a priori que $\vec{x}$ es escasa. El sparsest solución del sistema lineal puede obtenerse en el polinomio mediante la resolución de la optimización convexa $$ \min |\vec{x}|_1 \text{ s.t. } A\vec{x}=\vec{b} $$

El número de ratas que se requiere aquí es $\mathcal{O}(s \log(N))$ donde $s$ es el número de botellas de veneno.

Answer 5

Para el caso de una botella envenenada me sería de esperar que la respuesta sea logbase2(N), ya que podría tener cada rata beber de las botellas cuyas posiciones' dígitos binarios incluyen la rata de la posición y de las ratas que mueren serán aquellos cuyos puestos de dar la representación binaria de los malos de la botella de la posición.

Si que es correcta, entonces para dos malas botellas yo estaría inclinado a pensar en hacer lo mismo con la lista de todos botella de parejas, pero por supuesto que no es sólo una venenosa par. Con el fin de identificar la única doblemente venenosas par necesitamos reemplazar las ratas por algo que solo muere si tiene una dosis doble. Parece que los pares de ratas sería suficiente para que este, pero, a continuación, el número total necesario sería 2*logbase2(NC2) que sólo da 38 para N=1000, así que si tu respuesta es óptima debo haber perdido algo.

¿De dónde me salen mal?