Skip to main contentSkip to solution

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

✅ Correct Option: 2

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 nn tests, we can distinguish at most 2n2^n possibilities.

26=64<1002^6=64<100

27=128≥1002^7=128\ge100

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.

Keyboard Shortcuts

  • Left arrow: Previous question
  • Right arrow: Next question
  • S key: Jump to solution
  • Q key: Jump to question