1thanks for the solution sir
After elections, each senator in the CaliMass Congress has an absolute rating (the number of voters for example - anyway a positive number). Each of these senators enters in a committee in which he obtains a relative rating. The relative rating of a senator is the ratio between his absolute rating and the sum of all ratings in his committee (including his rating). A senator has the right to move from his committee to another committee if in this way his relative rating grows. In each day only one senator is allowed to change his committee. Prove that the senators cannot move for ever.
-
UP 0 DOWN 0 0 2
2 Answers
341Suppose there are m ≤ n committees where n is the number of senators
Let the sum of the absolute ratings of senators in committee i be represented by si
Suppose member k with abs rating xk is permitted to migrate. He will migrate to another committe sj if we have si-sj>xk (this follows from the condition for moving given)
Now consider the function F = Σ (sa-sb)2 summed over all pairs of committees. (you can also consider Σ |sa-sb|
The claim is that whenever a migration takes place this function decreases.
To see how, first consider the two committees between which the migration takes place. Prior to migration the summand is (si-sj)2 and subsequent to migration it is (si-sj-2xk)2 and since we have si-sj>xk it follows that (si-sj)2 > (si-sj-2xk)2
Again consider any other committee st
Prior to migration the summand is (si-st)2 +(sj-st)2 and subsequent to migration it is (si-st-xk)2 +(sj-st+xk)2 and again since si-sj>xk we have (si-st)2 +(sj-st)2 > (si-st-xk)2 +(sj-st+xk)2
Thus we have a proved that the function F decreases with migration. But F takes only integer values and is bounded below by zero. Hence this migration cannot take place infinitely and will stop.