Доказать неравенство

[trostewus]

Есть $n$ позиций (ячеек). Два игрока. У первого $k$ фишек, у второго - $s, k \ge s$. Игроки распределяют все свои фишки по этим позициям (ячейкам), не зная распределения соперника. Наша цель - подсчитать выигрыш первого игрока - как сумму выигрышей на каждой позиции. К примеру, на кокой-то позиции первый игрок постаивл 5 фишек, а второй - 3. Выигрыш первого составит $5-3=2$. Если поставили по-равну или второй поставил больше - выигрыш на позиции считается НУЛЕВЫМ.
Пусть игроки расставили свои фишки. Получаем на $i$-ой позиции - $k_i$ фишек первого игрока и $s_i$ фишек второго игрока. $k_1+...+k_n=k, s_1+...+s_n=s$.
Получаем функцию выигрыша на каждой позиции: $f(k_i,s_j)=\begin{cases} k_i-s_i,&\text{если $k_i>s_i$;}\\ 0,&\text{если $k_i \le s_i$.} \end{cases}$
Так вот в ходе решения задачи возникла необходимость доказать следующее утверждение:
$\[\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {f(k_i,s_j)}} \] \le nk-s$
Пытаюсь как-то к этому придти - не получается..может есть у кого-нибудь какие-либо идеи?..

[mihiv]

Пронумеруем числа $k_i,s_i$ в порядке возрастания:$k_1\leq \dots \leq k_n,s_1\leq \dots s_n$.Двойную сумму обозначим $R$. Если $s=0$,то выигрыш 1-го игрока в каждой ячейке равен $k_i$ и $R=nk$.
Пусть $s\neq 0$.Предположим $k_n>s_n$(и,следовательно $k_n>s_i$ для всех $i$).Во внешней сумме рассмотрим слагаемое $\sum \limits _{j=1}^nf(k_n,s_j)=nk_n-s$(в случае $s=0$ мы получили бы $nk_n$),т.е. сумма $R$ уменьшится по крайней мере на $s$.Следовательно $R\leq nk-s$.
Пусть теперь $k_n\leq s_n$(и,следовательно,$k_i\leq s_n$ для всех $i$).

В этом случае $\sum \limits _{i=1}^nf(k_i,s_n)=0$,(т.к. $k_i\leq s_n)$,тогда как при $s=0$ получили бы,что эта сумма равна $k$.Видим,что по сравнению со случаем $s=0$ двойная сумма уменьшилась по крайней мере на $k$Т.е. $R\leq nk-k<nk-s$.
Осталось заметить,что $R=nk-s$ при $k_n=k,k_i=0,1\leq i\leq n-1$.

[trostewus]

Спасибо большое! Я доказал еще одним способом, немного другим. Но Ваш тоже пригодится!