Switch it on

Logic Level 3

You have a lamp which needs $3$ batteries to run. You have $10$ batteries in total out of which $5$ are working batteries and the rest are dead. But you don't know which one is working or dead.

What is the least possible number of tries to check the batteries so that you are guaranteed to get a working triplet ?

[ Note :- The last try will not be considered if the result is sure.]

19 23 6 120

3 solutions

Mohd. Hamza
Mar 18, 2019

Divide the batteries into 2 sets of 5 each. Try checking batteries in the first set (10 tries). If it didn't work then set 2 is guaranteed to have at least one working triplet. In worst case we have to check set 2 $10$ times. So we have a total of 20 tries. But note that in 20th try we are guaranteed to get a working triplet. We have tried $19$ times in all !

Thanks to Mark Hennings for the solution.

That certainly works, but can you show that it can't be done in 18 or fewer tries?

Jordan Cahn - 2 years, 2 months ago

Nice question indeed.

But you see that 19 tries are at most required to be sure. There is also a strong possibility that we can get a working triplet in less than or equal to 18 tries.

I understand that you want me to prove that we can't be sure in at most 18 or less tries. But sadly I am unable to do so !

Mohd. Hamza - 2 years, 2 months ago

This is definitely a cool way to get the number down to 19, but... I feel that this is only half of the solution, that 19 is an upper bound for how many attempts we would need.

To be complete it would be nice to show that it is also a lower bound...

Geoff Pilling - 2 years, 2 months ago

According to me 19 can't be the lower bound because we need at most 19 tries. There is a strong possibility to get a working triplet less than or equal to 18 tries.

Mohd. Hamza - 2 years, 2 months ago

Isn't this basically the Ted-Ed riddle?

Jonathan Tse - 2 years, 2 months ago

Yes it is based on that. But different

Mohd. Hamza - 2 years, 2 months ago

The Ted-Ed one doesn't need all batteries to be working.

Elliott Chen - 1 year, 10 months ago

Alex Burgess
Mar 27, 2019

Can't prove $19$ is the minimum worst case either.

Perhaps "cheating" slightly (well quite a bit), you can do it in $5$ goes:

If the battery socket for the lamp can take up to 5 batteries, but only needs 3 to run:

Test the first 5 batteries: If success keep, if fail take the other 5.

Label batteries 1,2,3,4,5; and test 1,2,3,4.

If success test 1,2,3; 1,2,4; 1,3,4 if these fail then 2,3,4 work. (5 tests).

If fail, 5 works; test 2,3,4,5.

If success test 2,3,5; 2,4,5, if these fail 3,4,5 work (5 tests).

If fail, 1 works; test 1,5,2; 1,5,3, if these fail 1,5,4 works (5 tests).

I can prove that 5 is indeed the minimum: EDIT: I cannot, see below

there are 252 ways (10 choose 5) to divide the working batteries over all 10. So let's do 4 measurements (a measurement means seeing if the light goes off in a certain arrangement). After the first measurement, we get into two cases, and the worst case will have at least 126 ways in which the working batteries are divided over the 10 (we divided the 252 ways over the two possible outcomes of the measurement, which means that if one of these cases has less than 126 ways in which the working batteries can be divided over the 10, we continue looking at the other case). After another measurement, we will get at least 63 cases to consider in the worst case. After this, 32, and then 16.

Now we need to point at 3 batteries such that we can be sure that they are among the five working ones. We can make a right choice in 10 different ways (5 choose 3), which is the same as having 10 attempts at correctly identifying the 5 working batteries. However, we need 16 such attempts in the worst case if we are only given four measurements.

Sebastiaan Joosten - 1 year, 8 months ago

I made an error in my above reasoning. We can actually point at 3 batteries such that we can be sure that they are among the five working ones in 21 different ways (7 choose 2), not 10. Unfortunately, this then invalidates my proof.

Sebastiaan Joosten - 1 year, 8 months ago

Ian Bowen
Jun 19, 2019

You begin by putting the 10 batteries in a line. The worst case scenario is that you get batteries in this order:

D1, W1, D2, W2, D3, W3, D4, W4, D5, W5

Then you put D1 and W1 in the first two slots and try putting every other battery in the third slot. Since all these combinations fail, you know that at least one of the batteries in the first two slots are dead, so you put them aside. You have tried 8 different combinations so far.

Then you put D2 and W2 in the first two slots and try putting the remaining 6 batteries in the third slot. Since all these combinations fail, you know that at least one of the batteries in the first two slots are dead, so you put them aside. You have tried 14 different combinations so far.

You then put D3 and W3 in the first two slots and try putting the remaining 4 batteries in the third slot. Since all these combinations fail, you know that at least one of the batteries in the first two slots are dead, so you put them aside. You have tried 18 different combinations so far.

You put D4 and W4 in the first two slots and put D5 in the third slot. Since this combination doesn't work, you know that there are only two possibilities for the remaining batteries (including the two in the first two slots):

{D4, W4, D5, W5} or {W5, W4, D4, D5}

In either case, you know that every even battery up to W4 must have been working. If not, you would have had a combination that would have worked. So you take any three of the batteries in those four even spots.

Thus, you have 20 attempts, the last of which worked. Since the problem stated that we are not counting the last attempt if it works, the answer is 19.

Switch it on

3 solutions

0 pending reports