Minimum average-case queries of q+1-ary search game with small sets

Given a search space S={1,2,…,n}, an unknown element x∗∈S and fixed integers ℓ≥1 and q≥1, a q+1-ary ℓ-restricted query is of the following form: which one of the set {A0,A1,…,Aq} is the x∗ in?, where (A0,A1,…,Aq) is a partition of S and |Ai|≤ℓ for i=1,2,…,q. The problem of finding x∗ from S with q+1-ary size-restricted queries is called as a q+1-ary search game with small sets. In this paper, we consider sequential algorithms for the above problem, and establish the minimum number of average-case sequential queries when x∗ satisfies the uniform distribution on S.