There are $N$ identical boxes, each containing either a red or a blue ball. It is known that $M$ out of $N$ balls are red, and rest are blue. Alice and Bob plays a game. Alice has access to all boxes. Bob can take multiple guesses. At each turn, Bob chooses two boxes. If the two balls in those boxes are red, Alice says YES, in other cases she says NO. The game stops when Alice says YES for the first time. What is the minimum number of guesses required to ensure Alice to say YES as soon as possible?
For example if $N=5$ and $M=3$, Bob needs $4$ guesses. Consider this sequence of boxes selected by Bob – {red, blue}, {red, blue}. Last box must be red. Choose that box and check with boxes from one of the two previous guesses.
Another example, if $N=3$ and $M=2$, Bob needs $3$ guesses. Of the first guess is {red, red}, we are done. If the first guess is {red, blue}, last box must have red ball. Make the last two guesses with the third box and one box from previous guess. At most three guesses are required.
If $N=4$ and $M=2$, the answer should be $\leq 6$ and for $N=8$ and $M=4$, the answer should be $\leq 8$. Here is the explanation for $N=8$ and $M=4$. If Bob's first four guesses are {red, blue}, those cover all the boxes. Bob will take any two pairs and need another four guesses to cross-check.
In fact Bob can use only $7$ guesses! Bob will take any $3$ boxes and makes three pair-wise guesses. If all are 'N0', that means at least two of those boxes have blue balls. Bob take another three boxes, and exact same thing can happen in the worst case scenario. So he eliminates $4$ blue balls, so remaining two boxes must have red balls. So only $7$ guesses are needed for $N=8$ and $M=4$.
Is it possible to get a general form for any $N$ and $M$?
Best Answer
I think Ross Milikan's answer is incomplete. It doesn't seem to cover the (8,4) case you mention. Call f(N,M) the number of guesses you seek.After a bit of trial I find that I can break it down into four cases: $$ \begin{array}{cc} (i) & \quad f(N,2) = \binom{N}{2}\\ (ii) & \quad M > N - \lfloor N/2 \rfloor \implies f(N,M) = N - M + 1\\ (iii) & N \textrm{ odd, } M = (N + 1)/2 \implies f(N,M) = 2 + (N - 1)/2 \\ (iv) & Otherwise\end{array} $$ In case $(iv)$ we have to do some recursion. You first set $f(N,M) = \binom{N}{2} - \binom{M}{2} + 1$, but then you check if you can make this guess any better as in your example from $f(8,4)$. For each $k$ for $k \in [3,\lfloor N/2 \rfloor ]$ Check if $$\binom{k}{2} + f(N-k,M-1) < f(N,M)$$ If so update $f(N,M)$ with this new value. Basically you can always take $k$ and check every pair. If these fail, then you know you had at most one red ball amongst them.