Puzzle

A room has n computers, less than half of which are damaged, others are good. It is possible to query a computer about the status of any computer. A damaged computer could give wrong answers. The goal is to discover a good computer in as few queries as possible.

Source

Heard from Arvind Arasu in 2000—2001.

Solution

*Randomized linear time algorithm*: Pick a computer at random. Ask all computers whether it is damaged or not. With probability at least half, one such round succeeds. So we need at most two rounds on average.

*Deterministic linear time algorithm*: Thanks to Pratik Poddar for this ingenious idea: Consider a chain of computers where each computer except the last announces the status (good or bad) of its successor in the chain. If all announcements are good and if there is at least one good computer in the chain, then the last computer is definitely good! Pratik's algorithm constructs such a chain as follows. Start off with an empty chain. Repeatedly affix one of the remaining computers to the end of the chain. If the resulting chain has at least two computers and if the penultimate computer announces that the last computer is bad, then remove both of these computers from the chain and discard them forever. A pair of discarded computers enjoys the following properties: (a) at least one of them must have been bad, and (b) both of them cannot be good. Since good computers are in the majority, the chain must be non-empty after all computers have been processed and there must be at least one good computer in that chain. The last computer in that chain must be good. The total number of queries (asking some computer the status of another computer) is exactly n-1.

(Flawed solution, pointed out by readers) A deterministic linear time algorithm: Form pairs of computers. Ask computers in a pair the status of each other. If the answers were (good, good), choose one of the two computers. Otherwise, discard both computers. In one such round, the number of computers would reduce by (almost) half, giving us overall linear time.

© Copyright 2008—2017, Gurmeet Manku.