Solution
= Solution
Write $M=\#H_N$, $X=\#C_N$, and $q=\mathbb P(X\geq\theta M/2)$. Since $0\leq X\leq M$,
$$
\theta M\leq\mathbb EX
\leq\frac{\theta M}{2}(1-q)+Mq.
$$
Thus $q\geq(\theta/2)/(1-\theta/2)\geq\theta/2$.
= Solution
Write $M=\#H_N$, $X=\#C_N$, and $q=\mathbb P(X\geq\theta M/2)$. Since $0\leq X\leq M$,
$$
\theta M\leq\mathbb EX
\leq\frac{\theta M}{2}(1-q)+Mq.
$$
Thus $q\geq(\theta/2)/(1-\theta/2)\geq\theta/2$.