I don't understand what specific methods you're labeling as 5A and 5B
here. (If they're different methods to approach the same scenario, then
clearly 5B could "be better": you could replace it with 5A.)
Taking the same sort of constructive approach that I labeled (4) above
(4 dead / 4 alive), and applying it to the case of 5 dead / 3 alive:
* Test AB CD EF GH. Worst case is that they all fail, meaning that the
5 dead batteries include one from AB, one from CD, one from EF, and
one from GH.
* Test AC AD BC BD. Worst case is that they all fail, meaning that the
5 dead batteries include either (both A and B) or (both C and D).
* Test EG EH FG FH. Worst case is that the first three fail, meaning
that E and G are dead, in which case FH succeeds (test #12).
I'm guessing that this is what you meant by 5A. 5B remains unclear.
> in these problems, we are trying to reduce the # of moves in the worst case.
>
> Do we have interesting (new) genre of problems, if we instead
> tried to reduce the # of moves in the average case ?
Interesting to someone, I'm sure; but while I would not be confident of
(worst case 4 of 8 dead) or (worst case 5 of 8 dead) without running a
brute-force computer analysis, I wouldn't even attempt this new type of
problem without such an analysis.
In each case, if there are X batteries (Y of which are dead), then we
have:
* C(X, Y) possibilities for the subset of all dead batteries. These
are the possible scenarios that we could start in.
* N = C(X, 2) possibilities for pairs of batteries to test, thus
factorial(N) permutations of those pairs. These permutations are
the possible search strategies that we could follow.
Then compare every strategy in the second part to every scenario in the
first part, and calculate each strategy's worst case and average case.