Problem with black and white balls You are given $b+w$ boxes, $b,w$ of them contain a black or white ball inside, respectively. You want to find a pair of boxes with both balls black ($b\geq 2$). At each trial you make a guess of 2 boxes of your choice, and an Oracle tells you if both balls inside are black. If yes, you are done, if not, it just tells you "No", but does not reveal the contents of the boxes you chose.

Question: what minimal number of trials $n(b,w)$ do you need to guarantee that you find such a pair?

For $b>w$ there is a straightforward upperbound $n(b,w)\leq w+1$, which is achieved by dividing the collection into $\lceil (b+w)/2 \rceil$ pairs and trying them all one by one. The general upperbound is $n(b,w)\leq \binom{b+w}{2}-\binom{b}{2}+1$. I wonder if it can be improved by some clever box selection, and if there are some good lowerbounds.
 A: A better box selection process for minimal upper bound: 
Given $b$ and $w$, divide the boxes into $b-1$ groups as equally as possible. By the pigeonhole principle, at least one of the groups has 2 black-ball boxes, so test all possible pairs within each group. Do not test any pairs between groups. 
The upper bound to finding a black-ball pair is therefore approximately $$(b-1){\lceil \frac{b+w}{b-1}\rceil \choose 2}$$
The exact value depends on the number of groups of the two different sizes, of course - some of the groups are $\lceil \frac{b+w}{b-1}\rceil$ and some are one smaller, $\lfloor \frac{b+w}{b-1}\rfloor$. However this approach is effectively what is proposed in the case when $b$ is larger than $w$: arbitrarily choose $w+1$ groups of two which will yield a black pair, and the remainder can be regarded as "groups of one" which are not tested.
As an example, for $b=4, w=11$ we can divide into three groups of $5$ and need at most $$3{ 5 \choose 2} = 30 \text{ tests.}$$
By contrast, the upper bound calculated from the "all tests" option given in the question would be  $${15 \choose 2}-{4 \choose 2}+ 1 = 105 - 6+1 = 100 \text{ tests.}$$
Essentially, because we're concerned with the worst case, it doesn't matter we're removing some opportunities to have a pair of black boxes; the important thing is that we're cutting down on the number of tests that could give us a "No".
