Problem 3 IMOR 2018
Source: 2nd IMOR - 2018
July 13, 2018
IMORcombinatoricsalgebraic combinatoricsvector
Problem Statement
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 , and right when they seemed satisfied, Gugu arrived
with a serendipitous smile and proposed another configuration that achieved misery .
What is the maximum value of taken over all inputs to this problem?Proposed by Victor Reis (proglote), Brazil.