Number of steps in worst Case

Question

we have to run a song on a Walkman,for that we need 2 full batteries.Let s say we have a mixed set of 30 batteries (15 are emtpy and and 15 are full) and then only way to test if the battery full or empty is to put them in the Walkman and try it out.we can not tell which one is empty or full (one we put inside one full and one empty).

The question is to find the maxmium needed step to run the walkman (to find 2 full batteries)

I modelled the problem like that : let s that the Walkman is a function f which take two argumments and it return 1 it the walkman works ,and 0 otherwise. $$ f: \{b_1,b_2 \dots b_{30}\} \times \{b_1,b_2 \dots b_{30}\} \rightarrow\{0,1\}$$

The answer for the question was at most 18 steps , but somehow i could not figure it out. Any good suggestion how to proceed ?

Answer 1

You arrange your 30 batteries in pairs, where each pair consists of either:

• 2 empty batteries
• 2 full batteries
• 1 full and 1 empty battery

If you have a pair with 2 empty batteries it follows, that there is also a pair of 2 full batteries, thus, you have to test at most all of the pairs (15 steps) until you find a pair of two full batteries.

If your walkman isn't working after testing all 15 pairs, you know that each pair consists of a full and an empty battery. You take the first two pairs with batteries (a,b) and (c,d). You then try the pairings: (a,c), (a,d) and (b,c). You have now tested 18 combinations and either one of them worked or (b,d) has to be a working pair.

I don't know if this counts as 19 steps for your purposes (you have found 2 full batteries after 18 steps but the walkman is not running yet).