= Finite candidate elimination bound
Suppose a finite candidate <set> of size $N$ contains the truth, every query chooses a current candidate, and each wrong reply eliminates that candidate while retaining the truth. Then at most $N-1$ 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 $N-1$ replies. The proof is the strictly decreasing positive <cardinality> of the surviving candidate set after every nonidentifying round.
Back to article page
