The problem
You have a set on N (around 15-30) seemingly-identical objects, which in fact comprises a small number D (unknown, between 1-3) of defective objects and the rest (N-D) are good.
There is a test which can be performed on any chosen subset of the objects, which will reveal if the set contains at least one defective object. But the test is expensive, and only one test at a time can be carried out (multiple tests can't be run in parallel).
Your mission
Devise a testing strategy that will identify all defective objects as cheaply (on average) as possible. If there is a "well known" existing solution, that's fine, but I don't know it if so.
Origins of the problem
I have a new 18 core CPU that I'm overclocking core by core. A core that's overclocked will either be stable (its virtually never going to crash stuff running on it), or unstable (its likely to crash something running on it after a number of hours). The only way to test if the 18 cores are overclocked in a stable manner is to run a stress test program for some amount of time and see if it crashes or gives errors. Typically an hour under stress gives a good idea if any core will fail, but when you're done, you really need to stress test it for many hours if you want to be sure.
My current setup for the 18 cores runs nicely for an hour and I thought it was stable. But it failed when I tested it overnight for 12 hours. So 1 of the cores (or perhaps 2 or 3 at most) is in reality defectively tuned, although probably very close to correct.
I could try several things to find which core/s are defectively tuned.
- I could slightly unstress all but one core, for all 18 cores in turn, and run it for 18 x 12 hours at a time, and that would definitely reveal any defectively tuned cores.
- I could do the above, but when I find and fix any defectively tuned core, add an extra test run for 12 hours with all 18 cores stressed. That adds 1-3 x 12 hours of full retests, but also means if the mistuned cores happen to be 1+2, I don't waste 16 x 12 hours testing good cores after all the mistuned ones are fixed.
- I could test say 2 or 3 cores at a time for 12 hours. So I slightly unstress all but cores 1-3 and see if that works for 12 hours; there's low-ish odds that any specific group of 2-3 cores contains a mistuned core (and very low odds it contains >1 mistuned core), and this could eliminate 2-3 at a time not 1. The downside is, when a test crashes, I have to add further tests to find which core/s of those 2-3 were mistuned, it isn't immediately obvious.
- And so on.....
The trouble is, I don't really want to spend 3 weeks solid testing this thing. SO I'm looking for a better strategy.
The stated problem abstracts this situation, with N = 18, D is probably between 1 and 3, and the "cost" of a test is the time taken to thoroughly stress test for 12 hours, any selected subset of the 18 cores in the CPU.
(The problem simplifies somewhat by ignoring the option to do shorter or longer tests - for example test everything for 4 hours and see if that shows up defective tuning, then test for 12 hours to be sure. To an extent that can be modeled as a "cost" or 4 hours per test plus a 12 hour confirmatory run at the end. The reason is, I'm not certain that success/fail on a 12 hour run can be modelled as equivalent to 12 sequential 1 hour runs, statistically)