Задача из журнала «Квант» (2001 год, 4 выпуск)

Условие

Всякий депутат имеет свой (абсолютный) рейтинг. В начальный момент после избрания каждый депутат вошел в одну из фракций, в которой он может подсчитать свой относительный рейтинг. Возможен переход депутата из одной фракции в другую, если его относительный рейтинг при этом увеличивается. Пусть в каждый момент времени может происходить лишь один такой переход. Докажите, что спустя конечное время все рейтинговые переходы прекратятся.

Доказательство

Всякий $i$-й депутат имеет свой абсолютный рейтинг $R_{i}$. В начальный момент (после избрания) каждый $i$-й депутат вошел в одну из фракций, в которой он может подсчитать свой относительный рейтинг: $r_{i} = \frac{R_{i}}{S}$, где $S$ – сумма всех абсолютных рейтингов данной фракции.

Обозначим через $S_{i}\left(t\right)$, $S_{j}\left(t\right)$ суммы всех абсолютных рейтингов депутатов $i$ и $j$ фракций в момент $t$. Согласно условию переход $k$-го депутата (в момент $t$) из $i$-й фракции в $j$-ю реализуется, если и только если выполняется неравенство $\frac{R_{k}}{S_{i}\left(t\right)} < \frac{R_{k}}{S_{j}\left(t\right) + R_{k}}$ т.е $S_{i}\left(t\right) > S_{j}\left(t\right) + R_{k}$, или

$$R_{k} + S_{j}\left(t\right) — S_{i}\left(t\right) < 0 \tag{*}$$ Отметим, что здесь получаем $S_{i}\left(t+1\right) = S_i\left(t\right) — R_{k}$ и $S_{j}\left(t+1\right) = S_j\left(t\right) + R_{k}$.

Теперь рассмотрим функцию $L\left(t\right) = \sum S^{2}_{m}\left(t\right)$, где индекс $m$ пробегает все номера фракций. Покажем, что при реализации перехода $L\left(t\right)$ убывает. Действительно, пусть в момент $t$ происходит переход $k$-го депутата из фракции $i$-й во фракцию $j$-ю. Тогда получаем

$$L\left(t+1\right) = \left(S_{i}\left(t\right) — R_{k}\right)^{2} + \left(S_{j}\left(t\right) + R_{k}\right)^{2} + \sum S^{2}_{n}\left(t+1\right)$$ где $n$ отлично от $i$ и $j$. Раскрывая первые два квадрата и находим $$L\left(t+1\right) = S^{2}_{i}\left(t\right) + S^{2}_{j}\left(t\right) + 2R_{k}\left(R_k + S_{j}\left(t\right) — S_{i}\left(t\right)\right) + \sum S^{2}_{n}\left(t+1\right)$$ С учетом неравенства $\left(*\right)$ устанавливаем $L\left(t+1\right) < L\left(t\right)$. Но функция $L$ может принимать лишь конечное число значений, поэтому ее убывание не может продолжаться сколь угодно долго.

В.Ильичев