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, …, 2n}
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.