Maths Olympiad Prep

Library / /14 of 20

Algebra Difficulty 6.6 National olympiad Prove it China

Suppose there are mm questions in an examination attended by nn students, where m,n2m, n \ge 2 are given natural numbers. The marking rule for each question is as follows: if there are exactly xx students failing to answer the question correctly, then they will each get 0 marks, and those who answer it correctly will each get xx marks. The total marks of a student are the sum of marks he/she gets from the mm questions. Now rank the total marks of the nn students as p1p2pnp_1 \ge p_2 \ge \cdots \ge p_n. Find the maximum possible value of p1+pnp_1 + p_n.

Solution

For any k=1,2,,mk = 1, 2, \dots, m, assuming there are xkx_k students failing to answer the kkth question correctly, then there are nxkn - x_k ones who answer it correctly and each gets xkx_k marks from it accordingly. Suppose the sum of the nn students' total marks is SS. Then we have
i=1npi=S=k=1mxk(nxk)=nk=1mxkk=1mxk2. \sum_{i=1}^{n} p_i = S = \sum_{k=1}^{m} x_k (n - x_k) = n \sum_{k=1}^{m} x_k - \sum_{k=1}^{m} x_k^2.
As each student gets at most xkx_k marks from the kkth question, we have
p1k=1mxk.p_1 \le \sum_{k=1}^{m} x_k.
Since p2pnp_2 \ge \cdots \ge p_n, then pnp2+p3++pnn1=Sp1n1p_n \le \frac{p_2 + p_3 + \cdots + p_n}{n-1} = \frac{S - p_1}{n-1}.
Therefore,
p1+pnp1+Sp1n1=n2n1p1+Sn1n2n1k=1mxk+1n1(nk=1mxkk=1mxk2)=2k=1mxk1n1k=1mxk2. \begin{align*} p_1 + p_n &\le p_1 + \frac{S-p_1}{n-1} = \frac{n-2}{n-1}p_1 + \frac{S}{n-1} \\ &\le \frac{n-2}{n-1} \cdot \sum_{k=1}^{m} x_k + \frac{1}{n-1} \cdot \left( n \sum_{k=1}^{m} x_k - \sum_{k=1}^{m} x_k^2 \right) \\ &= 2 \sum_{k=1}^{m} x_k - \frac{1}{n-1} \cdot \sum_{k=1}^{m} x_k^2. \end{align*}
By the Cauchy Inequality, we have
k=1mxk21m(k=1mxk)2. \sum_{k=1}^{m} x_k^2 \ge \frac{1}{m} \left( \sum_{k=1}^{m} x_k \right)^2 .
Then
p1+pn2k=1mxk1m(n1)(k=1mxk)2=1m(n1)(k=1mxkm(n1))2+m(n1)m(n1). \begin{aligned} p_1 + p_n &\le 2 \sum_{k=1}^{m} x_k - \frac{1}{m(n-1)} \cdot \left( \sum_{k=1}^{m} x_k \right)^2 \\ &= -\frac{1}{m(n-1)} \cdot \left( \sum_{k=1}^{m} x_k - m(n-1) \right)^2 + m(n-1) \\ &\le m(n-1). \end{aligned}
On the other hand, if there is a student who answers all the questions correctly, while the other n1n-1 students fail to answer any questions, then we have
p1+pn=p1=k=1m(n1)=m(n1). p_1 + p_n = p_1 = \sum_{k=1}^{m} (n-1) = m(n-1).
Therefore, the maximum possible value of p1+pnp_1 + p_n is m(n1)m(n-1). \boxed{}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.