**Reference**:- Stelian Ciurea, Erik D. Demaine, Corina E. Pǎtraşcu, and Mihai Pǎtraşcu, “Finding a Divisible Pair and a Good Wooden Fence”, in
*Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004)*, Isola d'Elba, Italy, May 26–28, 2004, pages 206–219. **Abstract**:-
We consider two algorithmic problems arising in the lives of Yogi Bear
and Ranger Smith. The first problem is the natural algorithmic version
of a classic mathematical result: any (
*n*+ 1)-subset of {1, …, 2*n*} contains a pair of divisible numbers. How do we actually find such a pair? If the subset is given in the form of a bit vector, we give a RAM algorithm with an optimal running time of*O*(*n*/ lg*n*). If the subset is accessible only through a membership oracle, we show a lower bound of (4/3)*n*−*O*(1) and an almost matching upper bound of (4/3 + 1/24)*n*+*O*(1) on the number of queries necessary in the worst case.The second problem we study is a geometric optimization problem where the objective amusingly influences the constraints. Suppose you want to surround

*n*trees at given coordinates by a wooden fence. However, you have no external wood supply, and must obtain wood by chopping down some of the trees. The goal is to cut down a minimum number of trees that can be built into a fence that surrounds the remaining trees. We obtain efficient polynomial-time algorithms for this problem.We also describe an unusual data-structural view of the Nim game, leading to an intriguing open problem.

**Length**:- The paper is 12 pages.
**Availability**:- The paper is available in PostScript (178k), gzipped PostScript (72k), and PDF (105k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- DivisiblePair_SIGSAM (Finding a Divisible Pair)

See also other papers by Erik Demaine.

Last updated October 28, 2020 by Erik Demaine.