Suppose I have $n$ integers $\mu_i$ , $i=\{1,2,...,n\}$. Define $\bar{\mu}=\frac{1}{n}\sum_{i=1}^{n} \mu_i$. It is given that all the $\mu_i$'s are either $+1$ or $-1$. How can I show that $\sum_{i=1}^{n} (\mu_i - \bar{\mu})^2$ is maximized only when $\frac{\lfloor n \rfloor}{2}$ or $\frac{\lceil n \rceil}{2}$ are $+1$ and rest are $-1$'s.
I was thinking about proving this inductively, but I am not sure how.
Let $\phi(\mu) = \sum_k ( \mu_k - \bar{\mu})^2 = \sum_k \mu_k^2 - (\sum_k \mu_k)^2 $.
Since $|\mu_k| = 1$, we see that $\phi(\mu) = n- (\sum_k \mu_k)^2 $.
Hence $\phi$ will be maximised when $\mu \mapsto (\sum_k \mu_k)^2$ is minimised.
As an aside, note that this is also the solution to the relaxation $\max\{ \phi(\mu) \mid \mu_k \in [-1,1] \}$, which is convex. It is straightforward to see that ${\partial \phi(\mu) \over \partial \mu_k } = 2 (\mu_k-\bar{\mu})$ and ${\partial^2 \phi(\mu) \over \partial \mu_k^2 } = 2 (1-{1 \over n})$. In particular, we see that if $\mu_k \in (-1,1)$ then there is some $t$ such that $\mu+te_k$ is feasible and $\phi(\mu+te_k) > \phi(\mu)$. Hence at a maximum, we must have $|\mu_k| = 1$.