Maths Olympiad Prep

Track / Stage 6 / 315 of 400 #1315 of 1964

Problem 1315

National Olympiad, first round
Combinatorics Difficulty 6.5 Find the answer

nn students take a test with mm questions, where m,n≥2m,n\ge 2 are integers. The score given to every question is as such: for a certain question, if xx students fails to answer it correctly, then those who answer it correctly scores xx points, while those who answer it wrongly scores 00. The score of a student is the sum of his scores for the mm questions. Arrange the scores in descending order p1≥p2≥…≥pnp_1\ge p_2\ge \ldots \ge p_n. Find the maximum value of p1+pnp_1+p_n.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Next problem →

Official solution

1. Claim and Construction:
We claim that the maximum value of p1+pn p_1 + p_n is m(n−1) m(n-1) . To construct an example where this maximum is achieved, let every question be solved by the same person. In this case, the scores are:
p1=m(n−1),p2=p3=⋯=pn=0. p_1 = m(n-1), \quad p_2 = p_3 = \cdots = p_n = 0.
Thus, p1+pn=m(n−1)+0=m(n−1) p_1 + p_n = m(n-1) + 0 = m(n-1) .

2. Optimality Proof:
Let P1,P2,…,Pn P_1, P_2, \ldots, P_n be the students, with scores p1,p2,…,pn p_1, p_2, \ldots, p_n arranged in descending order. We need to show that:
p1+pn≤m(n−1). p_1 + p_n \le m(n-1).
To do this, we will prove a stronger statement:
p1+p2+p3+⋯+pnn−1≤m(n−1). p_1 + \frac{p_2 + p_3 + \cdots + p_n}{n-1} \le m(n-1).
This implies that p1+pn≤m(n−1) p_1 + p_n \le m(n-1) because pn≤p2+p3+⋯+pnn−1 p_n \le \frac{p_2 + p_3 + \cdots + p_n}{n-1} .

3. Score Analysis for Each Question:
Consider a single question q q . Let x x be the number of students who answered q q correctly. The score for each student who answered correctly is n−x n-x , and the score for each student who answered incorrectly is 0 0 .

4. Sum of Scores for Each Question:
For each question, the total score contributed by all students is:
x(n−x). x(n-x).
The score P1 P_1 obtained for this question is n−x n-x if P1 P_1 answered correctly, and 0 0 otherwise. The average score of the other n−1 n-1 students is:
(x−1)(n−x)n−1if P1 answered correctly, \frac{(x-1)(n-x)}{n-1} \quad \text{if } P_1 \text{ answered correctly},
or
x(n−x)n−1if P1 answered incorrectly. \frac{x(n-x)}{n-1} \quad \text{if } P_1 \text{ answered incorrectly}.

5. Bounding the Sum:
We need to show that for every question, the score P1 P_1 obtained plus the average score of the other n−1 n-1 students is at most n−1 n-1 . Consider the two cases:
- If P1 P_1 answered correctly:
n−x+(x−1)(n−x)n−1≤n−x+x−1=n−1. n-x + \frac{(x-1)(n-x)}{n-1} \le n-x + x-1 = n-1.
- If P1 P_1 answered incorrectly:
0+x(n−x)n−1≤n−1. 0 + \frac{x(n-x)}{n-1} \le n-1.
Since x(n−x)≤(n−1)(n−1) x(n-x) \le (n-1)(n-1) , the inequality holds.

6. Summing Over All Questions:
Summing the inequalities over all m m questions, we get:
p1+p2+p3+⋯+pnn−1≤m(n−1). p_1 + \frac{p_2 + p_3 + \cdots + p_n}{n-1} \le m(n-1).
Therefore,
p1+pn≤m(n−1). p_1 + p_n \le m(n-1).

Hence, the maximum value of p1+pn p_1 + p_n is m(n−1) m(n-1) .

The final answer is m(n−1) \boxed{ m(n-1) } .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.