$K$-Ary Searching With A Lie

Abstract

We determine the minimal number of queries sufficient to find an unknown integer $x$ between $1$ and $n$ if at most one answer may be erroneous. The admissible form of query is: “Which one of the disjoint sets $A_1,\dots ,A_k$ does $x$ belong to?”