Question 77
Let $a_{1}, a_{2}, \ldots, a_{n}$ be positive real numbers whose sum is equal to $1$. If
$$
\begin{aligned}
S= & \frac{a_{1}^{2}}{2 a_{1}}+\frac{a_{1} a_{2}}{a_{1}+a_{2}}+\frac{a_{1} a_{3}}{a_{1}+a_{3}}+\cdots+\frac{a_{1} a_{n}}{a_{1}+a_{n}} \\
& +\frac{a_{2} a_{1}}{a_{2}+a_{1}}+\frac{a_{2}^{2}}{2 a_{2}}+\frac{a_{2} a_{3}}{a_{2}+a_{3}}+\cdots+\frac{a_{2} a_{n}}{a_{2}+a_{n}} \\
& \vdots \\
& +\frac{a_{n} a_{1}}{a_{n}+a_{1}}+\frac{a_{n} a_{2}}{a_{n}+a_{2}}+\frac{a_{n} a_{3}}{a_{n}+a_{3}}+\cdots+\frac{a_{n}^{2}}{2 a_{n}}
\end{aligned}
$$
prove that $S \leq \frac{n}{2}$.
$$
\begin{aligned}
S= & \frac{a_{1}^{2}}{2 a_{1}}+\frac{a_{1} a_{2}}{a_{1}+a_{2}}+\frac{a_{1} a_{3}}{a_{1}+a_{3}}+\cdots+\frac{a_{1} a_{n}}{a_{1}+a_{n}} \\
& +\frac{a_{2} a_{1}}{a_{2}+a_{1}}+\frac{a_{2}^{2}}{2 a_{2}}+\frac{a_{2} a_{3}}{a_{2}+a_{3}}+\cdots+\frac{a_{2} a_{n}}{a_{2}+a_{n}} \\
& \vdots \\
& +\frac{a_{n} a_{1}}{a_{n}+a_{1}}+\frac{a_{n} a_{2}}{a_{n}+a_{2}}+\frac{a_{n} a_{3}}{a_{n}+a_{3}}+\cdots+\frac{a_{n}^{2}}{2 a_{n}}
\end{aligned}
$$
prove that $S \leq \frac{n}{2}$.