Putnam 2018, Problem A-3

Determine the greatest possible value of $\sum_{i=1}^{10} \cos(3x_i)$ for real numbers $x_1, x_2, \ldots, x_{10}$ satisfying $\sum_{i=1}^{10} \cos(x_i) = 0$.

Solution:
The maximum value is $480/49$. Since $\cos(3x_i)=4\cos(x_i)^3-3\cos(x_i)$, it is equivalent to maximize $4\sum_{i=1}^{10}y_i^3$ for $y_1,\ldots,y_{10}\in[-1,1]$ with $\sum_{i=1}^{10}y_i=0$; note that this domain is compact, so the maximum value is guaranteed to exist. For convenience, we establish something slightly stronger: we maximize $4\sum_{i=1}^ny_i^3$ for $y_1,\ldots,y_n\in[-1,1]$ with $\sum_{i=1}^ny_i=0$, where $n$ may be any even nonnegative integer up to 10, and show that the maximum is achieved when $n=10$.

We first study the effect of varying $y_i$ and $y_j$ while fixing their sum. If that sum is $s$, then the function $y\mapsto y^3+(s-y)^3$ has constant second derivative $6s$, so it is either everywhere convex or everywhere concave. Consequently, if $(y_1,\ldots,y_n)$ achieves the maximum, then for any two indices $i<j$, at least one of the following must be true:
- one of $y_i,y_j$ is extremal (i.e., equal to 1 or $-1$);
- $y_i=y_j<0$ (in which case $s<0$ and the local maximum is achieved above);
- $y_i=-y_j$ (in which case $s=0$ above).

In the third case, we may discard $y_i$ and $y_j$ and achieve a case with smaller $n$; we may thus assume that this does not occur. In this case, all of the non-extremal values are equal to some common value $y<0$, and moreover we cannot have both 1 and -1. We cannot omit 1, as otherwise the condition $\sum_{i=1}^ny_i=0$ cannot be achieved; we must thus have only the terms 1 and $y$, occurring with some positive multiplicities $a$ and $b$ adding up to $n$. Since $a+b=n$ and $a+by=0$, we can solve for $y$ to obtain $y=-a/b$; we then have
$$4\sum_{i=1}^ny_i^3=a+by^3=4a\left(1-\frac{a^2}{b^2}\right).$$

Since $y>-1$, we must have $a<b$. For fixed $a$, the target function increases as $b$ increases, so the optimal case must occur when $a+b=10$. The possible pairs $(a,b)$ at this point are $(1,9),(2,8),(3,7),(4,6)$; computing the target function for these values yields respectively $\frac{32}{9},\frac{15}{2},\frac{480}{49},\frac{80}{9}$, yielding $480/49$ as the maximum value.