Finite candidate elimination bound

ID: finite-candidate-elimination-bound

Suppose a finite candidate set of size contains the truth, every query chooses a current candidate, and each wrong reply eliminates that candidate while retaining the truth. Then at most wrong queries occur. If a correct reply uniquely identifies the truth, an infinite strategy of this kind eventually repeats the true candidate; stopping when only one candidate remains takes at most replies. The proof is the strictly decreasing positive cardinality of the surviving candidate set after every nonidentifying round.

New to topics? Read the docs here!