After elections, every parliament member (PM), has his own absolute rating. When the parliament set up, he enters in a group and gets a relative rating. The relative rating is the ratio of its own absolute rating to the sum of all absolute ratings of the PMs in the group. A PM can move from one group to another only if in his new group his relative rating is greater. In a given day, only one PM can change the group. Show that only a finite number of group moves is possible. (A rating is positive real number.)
Problem
Source: Romanian TST 2002
Tags: ratio, invariant, combinatorics proposed, combinatorics
05.02.2011 21:36
This is clearly a problem that asks for finding the right (semi)invariant! Denote the absolute rating of a PM $x$ by $r(x) > 0$. Say there are $n > 1$ groups $(G_k)_{1\leq k \leq n}$, all non-empty. Count the moves by $m=1,2,\ldots$. Then $s_0 = \sum_{k=1}^n \left (\sum_{x \in G_k} r(x) \right )$ is an invariant - the sum of all absolute ratings before any move was made, but the same after any number $m$ of moves, so $s_m = s_0$, constant. This is of no use. Let us rather consider the semi-invariant $\sigma_m = \sum_{k=1}^n \left (\sum_{x \in G_k} r(x) \right )^2$. Let us say at the next move a PM $x$ moves from a group $G$ to a group $H$. Denote by $a = \sum_{y \in G \setminus \{x\}} r(y)$ and by $b = \sum_{z \in H} r(z)$. Then it means the relative rating of $x$ increased, i.e. $\dfrac {r(x)} {a + r(x)} < \dfrac {r(x)} {b + r(x)}$, or $a>b$. Now it is easy to compute that $\sigma_{m+1} - \sigma_m = (b+r(x))^2 + a^2 - b^2 - (a+r(x))^2 = 2r(x)(b-a) < 0$, so $(\sigma_m)_{m\geq 0}$ is a decreasing sequence, lower bounded by $0$. But the value $2r(x)(a-b)$, by which it decreases at a move, cannot be too small! The possible sums of absolute ratings of a bunch of PM's can only take a finite number of values - for the $2$ power the total number of PM's of all possibilities (less $1$, for the empty set). Therefore $2r(x)(a-b) \geq \varepsilon > 0$ for some $\varepsilon$. By the principle of infinite descent, the number of possible moves is therefore finite, since $\sigma_m$ decreases by at least $\varepsilon$ at each move, while having to remain a positive number at all times.
06.02.2011 01:47
As always, it is a pleasure reading your post, mavropnevma. Although I'm guessing you meant $b =\sum_{z\in H}r(z)$, and moreover, this sum was taken after $x$ had moved.
06.02.2011 02:11
Correction made. But $b$ is correctly calculated before $x$ moves to $H$.
27.06.2021 15:09
Let the sum of all the absolute ratings in a group $G_i$ be called $S_i$. We claim that the product of all $S_i$s is a monovariant. Let’s say that a PM with absolute rating $a$ can move from $G_1$ with the sum of absolute ratings being $x$ to $G_2$ with the sum of absolute ratings being $y$. This must mean that $\frac{a}{x}<\frac{a}{a+y}$. Therefore, we get $a+y<x$. Consider the quantity $(x-a)(y+a)=xy+ax-a^2-ay=xy+a(x-a)-ay > xy+a(y)-ay=xy$. Hence the total product is always increasing. However, it’ll have to stop as the quantity (product of $S_i$s) is bounded from above. (Because the number of PMs is a finite number)
27.06.2021 17:25
Let $P$ be the set of all PM, i.e. the parliament and for any $x\in P$ let $r(x)$ be the rating of $x$. Consider the set $$D=\left\{\Delta := \frac{r(a)}{r(a)+\sum_{x\in X} r(x)}-\frac{r(a)}{r(a)+\sum_{y\in Y}r(y)}\mid \Delta>0; a\in P; X,Y\subset P; a\notin X; a\notin Y \right\}$$Thus, $D$ consists of finitely many positive numbers, so it has a minimal (positive) element, denote it by $\Delta$. Any time a PM jumps from one group to another its relative rating jumps by at least $\Delta.$ Suppose now, for the sake of contradiction, the infinite number of moves are possible. In this case there exists a PM which jumps forever from one group to group. Each time its relative rating increases by at least $\Delta.$ Therefore, at some moment it would be greater than $1$, contradiction.
23.08.2021 17:25
Product of sum of absolute ratings in groups is a monovariant...
06.08.2024 19:17
Not very hard to show that sum of sqaures of sum of absolute rating of groups is decreasing monovariant
08.12.2024 08:35
Messed up latex a bit will correct it later Say we are able to make a move of a person with number $x$, from room $A$, with sum of numbers $w_1$, originally, to room $B$, with sum of numbers $w_2$ originally. That means, $$\frac{x}{w_1} < \frac{x}{w_2 + x} \implies w_1 > w_2 + x$$We claim that the sum of squares of the sum of the numbers in each room decreases during this move. $$w_1^2 \implies (w_1 - x)^2, \\ \text{decrease is} \\ \\ 2w_1x - x^2$$$$w_2^2 \implies (w_2 + x)^2, \text{increase is} \\ 2w_2x + x^2$$So, the $\text{decrease} \\ - \\ \text{increase} = 2x(w_1 - w_2) - 2x^2 = 2x(w_1 - w_2 - x) > 0$ as $w_1 > w_2 + x$. Hence proved. So, if we are able to perform infinitely many moves, the sum of squares of the sum of the numbers in each room eventually goes below $0$, a clear contradiction.