Discrete Search with Directional Information

An unknown number N of cells are arranged in numerical order. An object is hidden in cell N. The problem is to locate the object—thereby determining N—within n searches. We consider a version of this problem that has applications in several problem settings: locating flaws in a discrete circuit, locating nerve endings, or locating the end of a tree root. A search of a site determines whether a cell is present and contains the object, except that it might overlook, with known probability w, a cell that is present; that is, a cell can “wink.” A search of site i reveals an empty cell if i < N; the cell containing the object if i = N and the cell does not wink; and no cell if i > N or if i ≤ N and the cell winks. Various special cases are considered. We define “bisection strategies” and show that they are optimal when w = 0. When w > 0, we partially characterize optimal strategies when n = 2, and completely characterize optimal strategies when there are at most two cells. For various values of n and w we give tables of the probability of finding the object for three intuitively reasonable strategies.