  It is a common contention that it is an ``impossible mission'' to exactly
determine the minimum sample size for the estimation of a binomial parameter
with prescribed margin of error and confidence level. In this paper, we
investigate such a very old but also extremely important problem and
demonstrate that the difficulty for obtaining the exact solution is not
insurmountable. Unlike the classical approximate sample size method based on
the central limit theorem, we develop a new approach for computing the minimum
sample size that does not require any approximation. Moreover, our approach
overcomes the conservatism of existing rigorous sample size methods derived
from Bernoulli's theorem or Chernoff bounds.
  Our computational machinery consists of two essential ingredients. First, we
prove that the minimum of coverage probability with respect to a binomial
parameter bounded in an interval is attained at a discrete set of finite many
values of the binomial parameter. This allows for reducing infinite many
evaluations of coverage probability to finite many evaluations. Second, a
recursive bounding technique is developed to further improve the efficiency of
computation.
