Competition problem — Algebra — Maths Olympiad Prep

Library / /42 of 86

Algebra Difficulty 5.8 AIME, harder Prove it Estonia

There are $n$ lists of candidates taking part in elections. Let $h_i$ be the total number of votes given for the candidates of the $i$ th list. There are $M$ seats in the representative assembly.

Anna proposes the following system for delivering mandates: For each list, one computes a reference number $v_i = \frac{h_i}{a_i + 1}$ where $a_i$ is the number of mandates already given to the $i$ th list (initially $a_i = 0$ , i.e., the reference number of each list equals its number of votes). On every step ( $M$ times in total), one chooses the list with the greatest reference number (if several lists share the first place, one of them is chosen randomly) and adds one mandate to this list, after which the reference number of this list is recomputed.

Bert's idea for delivering mandates is to multiply the number of votes of every list by $M/K$ where $K = h_1 + \dots + h_n$ , whereby fractional results are rounded downwards. As rounding may cause some seats to be undelivered, he proposes multiplying all numbers of votes of the lists by some suitable coefficient $\beta$ , so that the number of mandates given to the $i$ th list would be $m_i = \lfloor \frac{\beta h_i M}{K} \rfloor$ where $m_1 + \dots + m_n = M$ .

Prove that if such coefficient $\beta$ exists then Anna's and Bert's methods lead to the same distribution of mandates.

Solution

Let the total number of mandates given to the $i$ th list be $m_i$ in the case of Bert's method and $m'_i$ in the case of Anna's method. Suppose that these methods result in different distribution of mandates. As the sum of numbers of mandates must be the same, we must have $m'_i > m_i$ for some $i = 1, 2, \dots, n$ and $m'_j < m_j$ for some $j = 1, 2, \dots, n$ . As the numbers of mandates are integers, we have $m'_i \ge m_i + 1$ and $m'_j + 1 \le m_j$ .

Consider the situation in the case of Anna's method immediately after the $i$ th list having obtained its last mandate. Before obtaining the last mandate, the $i$ th list had $m'_i - 1$ mandates and reference number $v_i = \frac{h_i}{(m'_i - 1) + 1} = \frac{h_i}{m'_i}$ ,

while the $j$ th list had at most $m'_j$ mandates, implying that $a_j \le m'_j$ and $v_j = \frac{h_j}{a_j+1} \ge \frac{h_j}{m'_j+1}$ . As the mandate was given to the $i$ th list, $\frac{h_i}{m'_i} \ge \frac{h_j}{m'_j+1}$ . Thus $\frac{h_i}{h_j} \ge \frac{m'_i}{m'_j+1}$ , implying that
$m_j \cdot \frac{h_i}{h_j} \ge m_j \cdot \frac{m'_i}{m'_j+1} \ge m_j \cdot \frac{m_i+1}{m_j} \ge m_i+1.$
On the other hand, from the specification of Bert's method we know that
$m_j \cdot \frac{h_i}{h_j} = \frac{h_i}{h_j} \cdot \left\lfloor \frac{\beta h_j M}{K} \right\rfloor \le \frac{h_i}{h_j} \cdot \frac{\beta h_j M}{K} = \frac{\beta h_i M}{K} < \left\lfloor \frac{\beta h_i M}{K} \right\rfloor + 1 = m_i + 1.$
This inequation contradicts the previous inequation. Hence both methods indeed lead to the same distribution of mandates.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.