AoPS - Problem

Source:

Tags: geometry, rectangle, inequalities, combinatorics unsolved, combinatorics

Goutham

31.12.2011 14:27

The seats in the Parliament of some country are arranged in a rectangle of $10$ rows of $10$ seats each. All the $100$ $MP$s have diﬀerent salaries. Each of them asks all his neighbours (sitting next to, in front of, or behind him, i.e. $4$ members at most) how much they earn. They feel a lot of envy towards each other: an $MP$ is content with his salary only if he has at most one neighbour who earns more than himself. What is the maximum possible number of $MP$s who are satisﬁed with their salaries?

Let this maximum be $M$ . Draw an arrow between 2 adjacent cells from the smaller to the greater . In this way get $180$ directed arrows . An obvious inequality that condition of problems implies is $180 \leq M + 4(100-M)$ . But we can improve our estimation by noticing 2 special $MP$s . The one who gets maximum salary , and who has minimum salary and lies at boundary of our rectangle . It gives us $180 \leq M + 4(100-M) - 2$ so $M \leq 72$ . The example when maximum attains is easy to construct now , because of how we've proceeded to get it .