When the IMO is over and students want to relax, they all do the same thing: download movies from the internet. There is a positive number of rooms with internet routers at the hotel, and each student wants to download a positive number of bits. The load of a room is defined as the total number of bits to be downloaded from that room. Nobody likes slow internet, and in particular each student has a displeasure equal to the product of her number of bits and the load of her room. The misery of the group is defined as the sum of the students’ displeasures. Right after the contest, students gather in the hotel lobby to decide who goes to which room. After much discussion they reach a balanced configuration: one for which no student can decrease her displeasure by unilaterally moving to another room. The misery of the group is computed to be $M_1$, and right when they seemed satisfied, Gugu arrived with a serendipitous smile and proposed another configuration that achieved misery $M_2$. What is the maximum value of $M_1/M_2$ taken over all inputs to this problem? Proposed by Victor Reis (proglote), Brazil.
Problem
Source: 2nd IMOR - 2018
Tags: IMOR, combinatorics, algebraic combinatorics, vector
14.07.2018 17:13
Hint: the answer is $9/8$, with the following construction.
14.07.2018 18:08
I was so excited when I saw an interesting-looking combi! Imagine my displeasure when I realized it was just a disguised inequality... First things to note - the total displeasure within each room is just the square of the load of the room. Hence, different configurations of students producing the same total load in each room have the same misery. Thus we'll try to investigate how low we can get $M_2$, while preserving the loads of each room. We can use a dumb bound here - by QM-AM, the misery is at least $\frac {T^2}n$, where $T$ is the total load and $n$ is the number of rooms. Let the score be the maximal value of $\frac {M_1}{M_2}$, over all possible ways of splitting up a set of fixed room totals into individual students. The score is hence bounded above by $\frac {n\sum a_i^2}{(\sum a_i)^2}$, where the $a_i$ are the given room totals, and $n$ is the number of rooms. We'll call this latter value the score potential of the distribution of the room-totals. Suppose the smallest room has a load $s$. Then every other room either contains a single student, or has a load of no more than $2s$. This is because a room with load $l$ has to have every student in there need at least $l-s$ bits, else they'd jump over to the smallest room and the configuration is thus not balanced. If $l > 2s$, then there's no way to cram more than $1$ such student into the room. Now suppose we consider a room-total distribution with the maximum possible score (an optimal distribution). If we have some room with a single student whose load is greater than $2s$ (letting it be $k$), then letting $T$ be the total overall load excluding that student, the minimum value of $M_2$ is $\frac{T^2}{n}+k^2$. However, since that student is by himself, we can remove him (and the room he's in) completely, and attain another balanced configuration. This reduces both $M_1$ and $M_2$ by $k^2$, and hence increases the score, arriving at a contradiction. Thus, in an optimal distribution, every room has at most double the load of the smallest room. In the above construction (3 rooms, two of which consist of three students of load $1$ each, and the third consisting of two students of load $3$ each), the score is $\frac 9 8$, as stated. We now aim to show that no distribution of room-totals has score potential above $\frac 9 8$, hence no possible situation can exceed that value in score. Suppose we have an optimal distribution of room-totals, and that its score potential is strictly greater than $\frac 9 8$. If two rooms exist whose total loads are both neither the smallest, nor twice that, we can decrease the lesser of the two by some amount and increase the greater of the two by the same amount, generating another valid distribution of room-totals with a greater score. Hence, (after some normalization factor), any optimal distribution of room-totals consists of $a$ rooms of load $2$, $n-a$ rooms of load $1$, and $1$ room of load $1 + \epsilon$ with $0 \le \epsilon \le 1$. Since the score potential is greater than $\frac 9 8$, \begin{align*} \frac{n(n+3a+2\epsilon+\epsilon^2)}{(n+a+\epsilon)^2} &> \frac 9 8\\ 8n(n+3a+2\epsilon + \epsilon^2) &> 9(n+a+\epsilon)^2\\ 8\epsilon^2 n +6an &> n^2 + 9a^2+9\epsilon^2+2\epsilon n + 18 a \epsilon\\ 0 &> (n-3a)^2 +(2n+18a)\epsilon +(9-8n)\epsilon^2 \end{align*} We treat this as a quadratic in $\epsilon$. Since $n > 1$ (otherwise the score potential is trivially $1$), the coefficient of $\epsilon^2$ is negative. Hence, the minima of the $RHS$ must occur at $\epsilon = 0$ or $\epsilon = 1$. At $\epsilon = 0$, $RHS = (n-3a)^2 \ge 0$. At $\epsilon = 1$, $RHS = (n-3a -3)^2 \ge 0$. Hence the $RHS$ is always nonnegative, a contradiction. Hence $\frac 9 8$ is the maximal score potential, and thus the maximal possible score.