0

I've this problem:
Given a a list of frequencies $f_1 \geq f_2 \geq ... \geq f_n $ of $ n $ elements, such that $ \sum_{i=1}^n f_i = m $ where $ m $ is a multiple of $ n $. Prove that $ \sum_{i=1}^n i f_i \leq \frac{m(n+1)}{2}$.

Now I've proved that if all frequencies are equal this is true, in fact, if $ f_1 = f_2 = ... = f_n $ implies that $ f_i = m/n $ and so $ \sum_{i=1}^n i f_i = \frac{m}{n} \sum_{i=1}^n i = \frac{m}{n} \frac{n(n+1)}{2} = \frac{m(n+1)}{2}$

How to prove it when the frequencies are not all equals?

Pur2all
  • 60

1 Answers1

1

Let $(f_1,\ldots,f_n)$ be a list of frequencies with $\sum_{i=1}^nif_i$ maximal, and suppose it is not $(\frac mn,\ldots,\frac mn)$.

Then there must exist $1\le i_0<n$ such that $f_1\ge\cdots\ge f_{i_0}>\frac mn\ge f_{i_0+1}\cdots\ge f_n$ (otherwise, $\sum_{i=1}^nf_i$ would be either smaller or greater than $m$). Now, let $$\varepsilon:=\frac{f_{i_0}-f_{i_0+1}}2>0$$ and consider $$\widetilde{f_i}:=\begin{cases}f_i&\text{if $i\notin\{i_0,i_0+1\}$,} \\f_i-\varepsilon&\text{if $i=i_0$,}\\ f_i+\varepsilon&\text{if $i=i_0+1$.}\end{cases}$$ It is easily checked that $\sum_{i=1}^n\widetilde{f_i}=m$ and that $\widetilde f\!_1\ge\cdots\ge\widetilde f\!_n$. We find $$\sum_{i=1}^ni(\widetilde f\!_i-f_i)=-i_0\varepsilon+(i_0+1)\varepsilon=\varepsilon>0,$$ which contredicts the maximality of $(f_1,\ldots,f_n)$.

Thus $(\frac mn,\ldots,\frac mn)$ is the only list of frequencies for which $\sum_{i=1}^nif_i$ can be maximal. (One should also make sure that the maximum exists, but this is easily done by a compactness argument.)

nejimban
  • 3,663