Working Computer


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.


Heard from Arvind Arasu in 2000—2001.


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.

Previous Puzzle: Measuring Weights

(a) Customers at a grocer's shop always want an integral number pounds of wheat, between 1 pound and 40 pounds. The grocer prefers to measure wheat in exactly one weighing with a beam balance. What is the least number of weights he needs? (b) Customers come to a pawn shop with antiques. An antique always weighs an integral number of pounds, somewhere between 1 pound and 80 pounds. The owner of the pawn shop is free to do as many weighings as necessary to ascertain the unknown integral weight by using a beam balance. What is the least number of weights he needs?

A large regular hexagon is cut out of a triangular grid and tiled with diamonds (pairs of triangles glued together along an edge). Diamonds come in three varieties, depending on orientation; prove that precisely the same number of each variety must appear in the tiling.

12 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.