Let’s imagine that I have ten old computer circuit boards. Eight are in perfect condition, and two are defective.
Image: Konstantin Lanzet
I want to determine which are the two defective boards, and the only tool I have is an antiquated testing machine. To use the machine, I have to insert exactly three circuit boards, then push a test button. The test machine always gives a result and identfies a 'defective' board. Knowing what I do about the peculiarities of this test machine, here’s what could happen:
Because we know there are only two defective boards, there will never be a scenario where three defective boards are in the machine at the same time.
So, whatever the composition of states of boards inserted into the test machine, on every test, one circuit board will be classified as defective (sometimes correctly, but possibly incorrectly).
The test machine is agnostic of the ordering of the cards so there is no information that can be gained form knowing which slot any card was in when the test was run. Also, there is no information about the bias, periodicity, skew, or affinity when a card is selected at random, so any strategy involving repeating the same test multiple times and averaging the results is bogus.
Can you devise a strategy that will allow you to determine which two boards are defective? What is the smallest number of tests needed to perform this task?
Think about it for a while, then, when you think you have it, click the button to see a solution.