Maths Olympiad Prep

Track / Stage 6 / 260 of 400 #1260 of 1964

Problem 1260

National olympiad, first round
Combinatorics Difficulty 6.5 Find the answer

nn students take a test with mm questions, where m,n2m,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 p1p2pnp_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. Spacing, $ signs and \frac vs / are all fine.

Official solution

1. Claim and Construction:
We claim that the maximum value of p1+pn p_1 + p_n is m(n1) 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(n1),p2=p3==pn=0. p_1 = m(n-1), \quad p_2 = p_3 = \cdots = p_n = 0.
Thus, p1+pn=m(n1)+0=m(n1) 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+pnm(n1). p_1 + p_n \le m(n-1).
To do this, we will prove a stronger statement:
p1+p2+p3++pnn1m(n1). p_1 + \frac{p_2 + p_3 + \cdots + p_n}{n-1} \le m(n-1).
This implies that p1+pnm(n1) p_1 + p_n \le m(n-1) because pnp2+p3++pnn1 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 nx 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(nx). x(n-x).
The score P1 P_1 obtained for this question is nx n-x if P1 P_1 answered correctly, and 0 0 otherwise. The average score of the other n1 n-1 students is:
(x1)(nx)n1if P1 answered correctly, \frac{(x-1)(n-x)}{n-1} \quad \text{if } P_1 \text{ answered correctly},
or
x(nx)n1if 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 n1 n-1 students is at most n1 n-1 . Consider the two cases:
- If P1 P_1 answered correctly:
nx+(x1)(nx)n1nx+x1=n1. n-x + \frac{(x-1)(n-x)}{n-1} \le n-x + x-1 = n-1.
- If P1 P_1 answered incorrectly:
0+x(nx)n1n1. 0 + \frac{x(n-x)}{n-1} \le n-1.
Since x(nx)(n1)(n1) 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++pnn1m(n1). p_1 + \frac{p_2 + p_3 + \cdots + p_n}{n-1} \le m(n-1).
Therefore,
p1+pnm(n1). p_1 + p_n \le m(n-1).

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

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

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.