This is a question from a quantum computation textbook.
Consider a classical algorithm for counting the number of solutions to a problem. The algorithm samples uniformly and independently $k$ times from the Search Space of size $N$ for solutions using an Oracle that outputs 1 or 0, and let $X_1,X_2,X_3,...X_k$ be the results of the Oracle calls. So $X_j=1$ if the $jth$ Oracle call found a solution and $X_j=0$ otherwise. This algorithm estimates the number of solutions $S$:
$$S=N * \sum_{j}\frac{X_j}{k}$$
Assuming the number of solutions is $M$ and this is not known in advance. The Standard Deviation of $S$ is stated and found to be:
$$\Delta S=\sqrt{\frac{M(N-M)}{k}}$$
The question is:
Prove that to obtain a probability at least $\frac{3}{4}$ of estimating $M$ correctly to within an accuracy $\sqrt{M}$ for all values of $M$, we must have $k=\Omega(N)$.
I know how to get the 2nd equation from the 1st, which is by moving $N$ and $k$ to the left, thus treating $kS/N$ as a Binomial Distribution $B(k,\frac{M}{N})$. Then finding the variance of the Binomial Distribution and some algebraic manipulation will lead to the 2nd equation. I'm clueless in proving of $k=\Omega(N)$. Only thing I tried writing is:
$$P\Big(\sqrt{\frac{M(N-M)}{k}}\leq \sqrt{M}\Big)\geq \frac{3}{4}$$
Can someone help me with this?