A Chip Search Problem on Binary Numbers

摘要

Suppose that we have an unknown point d in the interval and an unbounded reservoir of chips on both points 0 and 1. In every step, we can either move two pebbles from points x and y to (x+y)/2, or we can ask whether dx, but only if there is currently a pebble at x. Our aim is to determine an interval of length 2 sup -n including d, and we are interested in the exact number of necessary moves in the worst case, especially for the firt values of n. First we analyze a natural GREEDY strategy solvign this problem in the other hand, n sup 2/12 is a lower bound. Our analysis allows to compute the exact worst-case number of moves g(n) that GREEDY takes for the first values of n, although a nice general expressio for this is missing. GREEDY sends pebbles only to points being binary approximatios of the target d. Moreover, our analysi will show that GREEDY is optimal among all strategie sharing this property. Hence any such strategy needs sita(n sup 2) moves in the worst case. It might seem that sending pebbles to other points brings no advnatages. So it is surprising that, without the mentioned restriction, we can achieve an asymptotic result of moves, by an acceleration technique. Hence GREEDY is not optimal in genral, nevertheless it seems to be the best choice for small n, since it is simple, and we have no strategy beating g(n) if n<20. An open problem is to determine the maximum n for which g(n) moves are optimal. In a final section we discuss a way to save tests if d is very small, and we briefly consider a variant of the problem where a test at x destroys a pebble lying there.