We use optional analytics, advertising and affiliate technologies to
measure usage, attribute advertising and improve EverythingQuant.
You can accept or reject non-essential tracking.
You have a bag of 101 computer chips. 50 of the chips have been exposed to cosmic radiation and are now bad. The chips can be used to test each other, so a good chip will respond with GOOD if it tests another good chip, and BAD if it tests a bad chip. However, a bad chip may or may not test another chip incorrectly.
How do you find one good chip from the bag while performing at most 99 tests? Assume the worst for your chips; i.e. whatever strategy you come up with, your strategy will be slowed by or you will pick the wrong chip.
Solution
Take chips one at a time and maintain a chain.
Start by taking two chips. Let the first chip test the second.
If the result is
\[
\text{BAD},
\]
discard both chips.
If the result is
\[
\text{GOOD},
\]
place both chips into a chain.
Now repeatedly take the next chip from the bag and have the last chip in the chain test it.
If the result is
\[
\text{GOOD},
\]
append the new chip to the chain.
If the result is
\[
\text{BAD},
\]
discard both the tester (the last chip in the chain) and the tested chip.
If the chain becomes empty, start again with the next two chips.
Observation:
If a good chip ever appears in the chain, then every chip that appears after it must also be good.
This is because a good chip would report
\[
\text{BAD}
\]
if it ever tested a bad chip, which would cause both to be discarded.
Therefore a bad chip can never remain after a good chip in the chain.
Also note that whenever the result is
\[
\text{BAD},
\]
at least one of the two chips involved must be bad. When both are discarded, we remove at least one bad chip.
Since there are \(101\) chips with \(50\) bad and \(51\) good, and we always discard chips in pairs containing at least one bad chip, the remaining pool always contains a majority of good chips.
Eventually the chain grows longer than the number of chips remaining in the bag. At that point there cannot be enough bad chips left to fill the entire chain.
Therefore the last chip in the chain must be good.
Each new chip is tested at most once when it leaves the bag, and at least one chip is discarded whenever a test fails. With \(101\) chips total, the worst-case number of tests required is
\[
99.
\]
Thus this procedure always finds a good chip using at most \(99\) tests.