Smashed Computers

Time to solve the broken computers problem. The solution isn't very hard to come by if you try to solve the lower N cases first. For N=1 and N=2, the problem is trivial (there aren't any broken computers), so the first real case is N=3. Label the computers A, B, and C:
Have computer A run a diagnostic on computer B. If it says B is working, then it is, if it says B is broken, then C is working.

This is simple enough, as if A says B is broken then either A or B is broken, if A says B is working then either B is working or both are broken. But we know there is only 1 broken computer.

Note that we do not need to worry about cases with even values of N since over half the computers are working, you can just throw one computer out the window and have one more diagnostic than you actually need without hurting your majority of working computers.

Anyway, our N=3 case gives us two hints for the main solution. One, if you have a chain of computers N1 to Nk where each one says the next one is working (specifically Ni says Ni+1 is working) then either they are all broken or the final one is working. So, if k>N/2 they cannot all be broken and so Nk is working. Next, if you have a computer that says another computer is broken, at least one of them is broken so you can throw both out the window and not lose your majority of working computers.

So, thats basically the solution:
Create a chain of computers, at each stage have the computer at the end of the chain run a diagnostic on a new computer. If the new computer is said to be working, add it to the end of the chain. If it is said to be broken, discard it along with the computer that ran the diagnostic on it. If the chain is ever empty, select a new computer to start the chain. If the chain is ever longer than half the computers you have left, the computer at the end is working.

You basically can prove by induction that this will work for N computers. The worst case with throwing computers away is that you lose a step in the chain so you actually spend two diagnostics. However, you got rid of two computers, so you have simply reduced to the case N-2 and have N-4 diagnostics. Since the solution works in the base case of N=3, it works all the way up odd values of N.

No comments: