Exactly one of 100 cables is faulty. The cables can be tested in groups with any number of cables in a group. A tester can be connected to any group of cables and reports only whether the faulty cable lies somewhere in that group. Each test may be chosen after seeing the result of the one before it. What is the least number of tests that guarantees finding the faulty cable?
Exactly one of 100 cables is faulty. The cables can be tested in groups with any number of cables in a group. A tester can be connected to any group of cables and reports only whether the faulty cable lies somewhere in that group. Each test may be chosen after seeing the result of the one before it. What is the least number of tests that guarantees finding the faulty cable?
Solution
Each test has only two possible outcomes:
- the faulty cable is in the tested group;
- the faulty cable is not in the tested group.
So with tests, we can distinguish at most possibilities.
Therefore, 6 tests cannot always identify the cable, while 7 tests are enough by repeatedly splitting the remaining possibilities into two nearly equal groups.
Hence, the minimum is 7 tests.
Related questions:
2026: Actual Paper
2026: Sample Paper
2026: Sample Paper