A. Pelc, Weakly adaptive comparison searching,
*Theoretical Computer Science* 66 (1989), pp. 105-111.

Abstract:

We consider schemes of discrete search in the set {1, ..., *n*} using
only comparison queries, i.e., those of the
form ``* x < a?*''. Such a scheme is called *i*-adaptive
if questions may be stated in *i*
series, so that answers are obtained after each series but not
between particular questions in it. We describe a worst-case optimal
algorithm of *i*-adaptive search and determine its complexity. The
latter turns out to be *in ^{1/i}*, where

A. Pelc, Detecting a counterfeit coin with unreliable weighings,
*Ars Combinatoria* 27 (1989), pp. 181-192.

Abstract:

We provide a worst case shortest procedure to find one counterfeit
heavier coin among identically looking coins when a beam balance can
be used and at most one weighing result can be erroneous. The exact
minimal number of weighings is shown. Its asymptotic behaviour for *n*
coins is *log _{3}n +O (log log n)*.

J. Czyzowicz, D. Mundici, A. Pelc, Ulam's searching game with lies,
*Journal of Combinatorial Theory, Series A*, 52 (1989), pp. 62-76.

Abstract:

We determine the minimal number of yes-no queries sufficient to find
an unknown integer between 1 and *2 ^{n}*, if at most two of the answers may be erroneous.

A. Pelc, Detecting errors in searching games,
*Journal of Combinatorial Theory, Series A*, 51 (1989), pp. 43-54.

Abstract:

We consider two-person searching games handling erroneous
information. The Responder selects a number from {1, ..., *n*}, unknown
to the Questioner, who has to find it asking yes-no questions. The
Responder may lie up to *k* times during the entire search. In the
first game the Questioner wins if he finds the unknown number or if
he can prove that some answers were false. In the second game he also
needs to determine the number of lies if they occurred. We study
optimal winning strategies of the Questioner and determine their
lengths. The results are compared to those about the minimal length
of a *k*-error detecting code of given size.

A. Pelc, Searching with known error probability,
*Theoretical Computer Science* 63 (1989), pp. 185-202.

Abstract:

We study the problem of interactive searching in a set of numbers,
using comparison queries, under the assumption that each answer can
be erroneous with a constant probability *p* and that a given
reliability * 0 < q < 1 * of the result is required. The search is
considered in three versions: continuous (the search space is the
interval [0, 1] and the unknown real *x* has to be found with a given
accuracy *1/n*, discrete bounded (*x* is an element of
{1, ..., *n*}) and discrete
unbounded (the unknown number *n* can be any positive integer). We
prove that in all cases the search is feasible for any *n*
and *q* iff *p* is different from 1/2. For such *p*, an *O(log n)* searching algorithm is given
in the continuous case and *O(log ^{2}n)* algorithms
in the discrete bounded and unbounded cases. For