Bay Area Mathematical Olympiad

Solution:

Inspecting a few values leads one to the correct guess that equality holds if and only if $n$ is a power of $2$. The idea is to use induction by "doubling" to prove the result. When $n=1$, we have $1=1$ as desired. Now suppose $n \geq 2$. If $n=2k$ with $k \geq 1$, then
$$\begin{aligned} b_{n} & =\left(a_{1}+a_{3}+\cdots+a_{2k-1}\right)+\left(a_{2}+a_{4}+\cdots+a_{2k}\right) \\ & =1+3+\cdots+(2k-1)+\left(a_{1}+a_{2}+\cdots+a_{k}\right) \\ & =k^{2}+b_{k} \\ & \geq k^{2}+\left(k^{2}+2\right) / 3 \quad \text{ (by the inductive hypothesis) } \\ & =\left(n^{2}+2\right) / 3, \end{aligned}$$
with equality if and only if $k$ is a power of $2$, i.e., if and only if $n$ is a power of $2$. If instead $n=2k+1$ with $k \geq 1$, then
$$\begin{aligned} b_{n} & =\left(a_{1}+a_{3}+\cdots+a_{2k+1}\right)+\left(a_{2}+a_{4}+\cdots+a_{2k}\right) \\ & =1+3+\cdots+(2k+1)+\left(a_{1}+a_{2}+\cdots+a_{k}\right) \\ & =(k+1)^{2}+b_{k} \\ & \geq(k+1)^{2}+\left(k^{2}+2\right) / 3 \quad \text{ (by the inductive hypothesis) } \\ & =\frac{(2k+1)^{2}+2}{3}+\frac{2k+2}{3} \\ & >\left(n^{2}+2\right) / 3 \end{aligned}$$
so strict inequality holds, as desired.