Can 90% Of People Do Better Than Average?

In these problems, in order to maximize the number of students admired by his peers, you want to maximize the number of students with a higher rating than just over half of their friends.

By intuition, each student would probably need an odd number of friends to maximize the number of admired students (since an even number of friends means the student needs a higher rating than at least 1 more than half of his friends while an odd number of friends means the student needs a higher rating than at least 1/2 more than "half" of his friends). You can probably prove that for an even number of students with a similar method of what I did for an odd number of students.

If each student has $2x+1$ friends ( $x$ is a non-negative integer), they would need to have a higher rating than at least $x+1$ friends. The number pairs of friends is $\frac{600(2x+1)}{2} = 300(2x+1)$ . Each pair has one person higher than the other. Dividing the number of pairs by $x+1$ (and maximizing the expression some $x$ )was my first thought, but it wouldn't work because the person with the highest rating must have a higher rating than $2x+1$ friends, the person with the second highest rating must have a higher rating than at least $2x$ friends, etc.

After accounting for this issue, I found out that there were $(2x+1) - (x+2) + 1 = x$ students who must have a higher rating than more than $x+1$ friends. The (minimum) total number of friends who have a lower rating compared to them is $\frac{(2x+1)+(x+2)}{2}\times x = \frac{3}{2}x(x+1)$ .

We are left with a maximum of $\lfloor (300(2x+1) - \frac{3}{2}x(x+1)) \div (x+1) \rfloor$ students with $x+1$ friends that have a lower rating than them. We are now trying to find the maximum value of $\lfloor (300(2x+1) - \frac{3}{2}x(x+1)) \div (x+1) \rfloor + x$ .

Further simplifying it will give:

$\lfloor \frac{300(2x+1)}{x+1} - \frac{x}{2} \rfloor$

$\lfloor \frac{600(2x+1) - x(x+1)}{2(x+1)} \rfloor$

$\lfloor \frac{-x^2+1199x+600}{2(x+1)} \rfloor$

The maximum of this expression is between $23$ and $24$ , and plugging in $23$ and $24$ both give $\boxed{576}$ as the answer.

The final step is to show that this exists (following the construction). I'm not sure how to write this but you can show its existence with some pattern/symmetry for most students and that the top $x$ students are all friends with each other.

This is not a complete solution, but meant to get you started thinking.

Once again, there are 2 parts to this question. First, we have to figure out what the maximum is.

Let's try a simple approach. For each friendship, we will give a card of admiration to the student who performed better. Then, we have given out $\frac{1}{2} \times 600 \times 2k = 600k$ cards of admiration. An admired student must have at least $k+1$ such cards, hence the number of elated students is at most

$\frac{ 1}{k+1} ( 600k).$

This initial bound seems extremely useless, as with $k=299$ we get a bound of 598, which doesn't really help. However, if we consider the case of $k= 299$ , i.e. almost everyone is friends with everyone else, then it becomes clear that approximately 50% of people can do better than the global average. Hence, the bound should actually be closer to 300, as opposed to 598.

The reason for this, is that some cards are 'wasted'. For the top student, we know that he has done better than all his friends, and hence has $2k$ cards. The next best student also has $2k$ or $2k-1$ cards. In fact, the $n$ th student has at least $2k- n$ cards. This over counting allows us to improve the bound, as the number of cards beyond $k+1$ that are wasted. This wastage is equal to $(k-1) + (k-2) + \ldots + 1 = \frac{k(k-1)}{2}$ . Hence, the 'true'/better bound, is

$\frac{1}{k+1} [ 600k - \frac{k(k-1)}{2} ] = 601 . 5 - ( \frac{600}{k+1} + \frac{k+1}{2} ) \leq 601.5 - \sqrt{1200} < 567.$

Great, so if we have $2k$ friends, then the number of admired students is at most 567.

However, since the answer is 576, it means we have to look at the scenario with $2k-1$ friends. I leave it to you to continue the analysis, and show that with $2k-1$ friends, we can have at most 576 students. Equality occurs (at best) with 47 friends.

Then, you have to construct an actual example, to verify that 576 can be achieved. Use the equality conditions enforced by the above bounding to help suggest a construction.