Suppose we have \(n\) batteries, \(g\) good ones, and a flashlight that takes \(c\) batteries. And you don't know which are the bad ones.
And, let \(f(n,g,c) =\) The minimum number of attempts (insertions of \(c\) batteries into the flashlight) you need in order to get your flashlight working.
And assume that the only way the flashlight will work is if all \(c\) batteries you put in the flashlight are good. Otherwise, it won't work, and there is no way to distinguish between any combination that contains one or more bad batteries.
What I am wondering is how to show/prove the general solution for \(f(n,g,c)\).
We have a few trivial cases:
So, I think the first non-trivial case becomes:
This one can be done in four moves, (1 vs 2, 3 vs 4, 4 vs 5, 3 vs 5) but can we prove that it can't be done in fewer?
And, does anyone have any idea about how we can solve this problem for the general case?