students take a test with questions, where are integers. The score given to every question is as such: for a certain question, if students fails to answer it correctly, then those who answer it correctly scores points, while those who answer it wrongly scores . The score of a student is the sum of his scores for the questions. Arrange the scores in descending order . Find the maximum value of .
Problem 1260
Official solution
1. Claim and Construction:
We claim that the maximum value of is . To construct an example where this maximum is achieved, let every question be solved by the same person. In this case, the scores are:
Thus, .
2. Optimality Proof:
Let be the students, with scores arranged in descending order. We need to show that:
To do this, we will prove a stronger statement:
This implies that because .
3. Score Analysis for Each Question:
Consider a single question . Let be the number of students who answered correctly. The score for each student who answered correctly is , and the score for each student who answered incorrectly is .
4. Sum of Scores for Each Question:
For each question, the total score contributed by all students is:
The score obtained for this question is if answered correctly, and otherwise. The average score of the other students is:
or
5. Bounding the Sum:
We need to show that for every question, the score obtained plus the average score of the other students is at most . Consider the two cases:
- If answered correctly:
- If answered incorrectly:
Since , the inequality holds.
6. Summing Over All Questions:
Summing the inequalities over all questions, we get:
Therefore,
Hence, the maximum value of is .
The final answer is .