This is Exercise 6.14 from Nielsen & Chuang.
Prove that any classical counting algorithm with a probability at least $3/4$ for estimating $M$ correctly to within an accuracy $c\sqrt{M}$ for some constant $c$ and for all values of $M$ must make $\Omega (N)$ oracle calls. Here $N$ is the size of the set, and $M \leq N$ are the number of elements which are the solution to the search problem.
I have been stuck on this problem for some time now. The key point is I do not really see how to do this for "any" classical algorithm. Any help would be much appreciated.
Statement of the Original Problem in Exercise 6.14 of Page 261, Quantum Computation and Quantum Information by Nielsen and Chuang
Consider a classical algorithm for the counting problem which samples uniformly and independently $k$ times from the search space, and let $X_1, ... ,X_k$ be the results of the oracle calls, that is, $X_j=1$ if the $j$ th oracle call revealed a solution to the problem, and $X_j=0$ if the $j^{th}$ oracle call did not reveal a solution to the problem. This algorithm returns the estimate $S≡N\times\sum_j X_j/k$ for the number of solutions to the search problem. Show that the standard deviation in S is $\Delta S=\sqrt{M (N − M )/k}$. Prove that to obtain a probability at least $3/4$ of estimating $M$ correctly to within an accuracy $\sqrt{M}$ for all values of $M$ we must have $k=\Omega(N)$.