## Ten Lanterns

You have ten lanterns, five of which are working, and five of which are broken. You are allowed to choose any two lanterns and make a test which tells you whether there is a broken lantern among them or not. How many tests do you need until you find a working lantern?

*Remark: If the test detects that there are broken lanterns, it does not tell you which ones and how many (one or two) they are.*

**SOLUTION**

You need 6 tests:

(1, 2) → (3, 4) → (5, 6) → (7, 8) → (7, 9) → (8, 9)

If at least one of these tests is positive, then you have found two working lanterns.

It all of these tests are negative, then lantern #10 must be working. Indeed, since at least one lantern in each of the pairs (1, 2), (3, 4), (5, 6) is not working. Therefore, there are at least 2 working lanterns among #7, #8, #9, #10. If #10 is not working, then at least one of the pairs (7, 8), (7, 9), or (8, 9) must yield a positive test, which is a contradiction.

With some case analysis, it is not hard to see that 5 tests are not enough.