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.

Articles by others on the same topic (0)

There are currently no matching articles.