Suppose a quality inspector is inspecting $b$ black amongst which $d_B$ are known to be defective and $w$ white gadgets amongst which $d_W$ are known to be defective. The gadgets come down along an assembly line one by one in uniformly distributed random order. As each gadget passes, the inspector observes its color, and he chooses to let the gadget pass or use a device to detect whether the gadget is defective. But he can only use the device a total of $n$ times. What is the optimal stopping rule to use the inspecting device to maximize the expected number of defective gadgets found.

**Edit:** As fedja points out below, there is a difference between detecting a defect by the device and deducing for sure by logic a defect. Both are legitimate objectives. The solution to the first is easier than that to the second. I for now choose the first definition, i.e., to define finding a defective gadget as only indicated by the device and use up one quota of using the device even if the quality inspector is sure by logic alone the gadget under inspection is defective.

Suppose at a pass the number of black gadgets already inspected by the device is $i_B$, amongst them $f_B$ are detected to be defective. Suppose the current passing gadget is black and yet to be inspected. Then the probability of this black gadget being defective is $p_B=\frac{d_B-f_B}{b-i_B}$. Symmetrical probability holds for if the current passing gadget is white.

I have a conjecture for the explicit solution, which is a greedy algorithm, as follows and am seeking a proof.

At a pass of the gadget, without loss of generality, suppose the current gadget which has not yet been inspected is black. Suppose there are $n_B$ black including the current one and $n_w$ white gadgets left. Suppose $i_B$ black and $i_W$ white gadgets have been inspected, amongst which $f_B$ black and $f_W$ have been found to be defective. If $p_B\ge p_W$ or $n_W=0$ the inspector inspect the current black gadget with the device. Otherwise, the inspector let the current black gadget pass without inspection.

I have set up the dynamic programming formulation but fail to see either the proof or a counterexample to my conjecture.

It seems only the case when, at least one color, is all defective would make a difference.In the recursive formula, yes, but it changes the answer even in the cases when we haven't arrived at that situation yet but are potentially close to it. The "beep objective" results in a cleaner recursion and simpler boundary conditions, so let's stick to it for now: I still do not see how to finish even this case :-) $\endgroup$9more comments