Problema con el blanco y negro de bolas

Question

Se le da $b+w$ cajas, $b,w$ de ellos contienen una negra o bola blanca en el interior, respectivamente. Usted quiere encontrar un par de cajas con dos bolas negras ($b\geq 2$). En cada ensayo que hacer una conjetura de 2 cajas de su elección, y un Oráculo le dice que si las dos bolas en el interior son de color negro. Si sí, usted está, si no, simplemente le dice "No", pero no revela el contenido de las cajas que usted eligió.

Pregunta: ¿qué número mínimo de ensayos de $n(b,w)$ ¿necesita la garantía de que usted encontrar una pareja?

Para $b>w$ no es un simple límite superior $n(b,w)\leq w+1$, la cual se logra mediante la división de la colección en $\lceil (b+w)/2 \rceil$ pares y tratando de todos ellos uno por uno. El general de límite superior es $n(b,w)\leq \binom{b+w}{2}-\binom{b}{2}+1$. Me pregunto si puede ser mejorado por la inteligente selección de cuadro, y si hay algunas buenas lowerbounds.

Answer 1

Un mejor cuadro de proceso de selección de mínima cota superior:

Dado $b$$w$, dividir las cajas en $b-1$ grupos tan iguales como sea posible. Por el principio del palomar, al menos uno de los grupos tiene 2 negro-bola de cajas, para probar todos los posibles pares dentro de cada grupo. No prueba de ninguna pares entre los grupos.

El límite superior para encontrar un negro de una pelota de pareja es, por tanto, aproximadamente el $$(b-1){\lceil \frac{b+w}{b-1}\rceil \choose 2}$$

El valor exacto depende del número de grupos de las dos tamaños diferentes, por supuesto - algunos de los grupos que se $\lceil \frac{b+w}{b-1}\rceil$ y algunos son uno de los más pequeños, $\lfloor \frac{b+w}{b-1}\rfloor$. Sin embargo, este enfoque es, efectivamente, lo que se propone, en el caso de $b$ es mayor que $w$: elegir arbitrariamente $w+1$ grupos de dos que conducirá a un negro par, y el resto pueden ser considerados como "grupos de uno", que no están probadas.

Como un ejemplo, para $b=4, w=11$ podemos dividir en tres grupos de a $5$ y necesidad en la mayoría de las $$3{ 5 \choose 2} = 30 \text{ tests.}$$

Por el contrario, el límite superior calculado a partir de los "todas las pruebas" opción dada en la pregunta sería $${15 \choose 2}-{4 \choose 2}+ 1 = 105 - 6+1 = 100 \text{ tests.}$$

Esencialmente, porque estamos preocupados con el peor de los casos, no importa estamos eliminando algunas de las oportunidades para tener un par de cajas negras; lo importante es que estamos reduciendo el número de pruebas que nos podría dar un "No".