= Solution
Put $v=t(1-t)$ and $M=\max_i\beta_i$. If $v=0$ the assertion is immediate. Otherwise, suppose
$$
M<\frac{v\log n}{2n}.
$$
Since $v\leq1/4$, this makes $M\leq\log n/(8n)$, so $M$ is sufficiently small to apply the <maximum-influence logarithmic lower bound> once $n$ is large. That bound gives
$$
nM\geq\sum_i\beta_i\geq\frac23v\log(1/M)
\geq\frac23v\left(\log n-\log\log n+\log8\right).
$$
For all sufficiently large $n$, the last quantity exceeds $v\log n/2$, contradicting $nM<v\log n/2$. The choice of sufficiently large $n$ is independent of $t$. Therefore
$$
\boxed{\max_i\beta_i\geq\frac12t(1-t)\frac{\log n}{n}.}
$$
Back to article page
