2

Question

$n$ students attend a test of $m$ problems where $m, n \ge 2$. The scoring rule for each problem is:

If $x$ students answer a problem incorrectly, then a correct answer worth $x$ points and an incorrect answer worth none.

The total score of a student is the sum of scores of all $m$ problems. The total score of all students will be arranged from high to low as $P_{1}\ge P_{2}\ge P_{3}\ge \cdots\ge P_{n}$.

What is the biggest possible value of $P_{1}+P_{n}$?

This problem is from china (2013.10.13) Mathematical olympiad problem on this morning.Now is the afternoon.

enter image description here

achille hui
  • 122,701
  • Could you write more clearly? I don't understand the question at all. – Ehsan M. Kermani Oct 13 '13 at 06:54
  • 1
    @EhsanM.Kermani the original question looks like the output from some online translator. I've translated the question myself based on the chinese test in the attached image. I hope my poor "engrish" translation is at least better than the one from a machine. – achille hui Oct 13 '13 at 07:08
  • @achillehui,Thank you very much help me translation. –  Oct 13 '13 at 07:09

2 Answers2

3

If one student answers every problem correctly and every other student answers every problem incorrectly, then $P_1 + P_n = (n-1) m$. I will show $P_1 +P_n \le (n-1) m$ for any set of answers, so the solution is $(n-1)m$.

Label the students $1,\ldots,n$ from highest score to lowest. Let $X_{ij} = 1$ if student $i$ answered problem $j$ incorrectly and 0 otherwise. Suppose student $w$ (for worst) answered fewer questions correctly than any other student (ties allowed). Let $r$ (for right) be the number of questions she answered correctly. I will show $ (n-1)m \ge P_1 + P_w$, from which it immediately follows $(n-1) m \ge P_1 + P_n$.

Assume without loss of generality that $w$ answered questions $1,\ldots,r$ correctly. Then

\begin{equation} P_1 = \sum_{i\ge 2, j} X_{ij} \\ P_w = \sum_{i\ne w, j=1,\ldots, r} X_{ij}. \end{equation}

Since each student answered at least $r$ questions correctly, $\sum_j X_{ij} \le m -r$ for any given $i$. Hence, \begin{equation} P_1 = \sum_{i\ge 2,j} X_{ij} \le (n-1)(m-r). \end{equation} Also, it is obvious that \begin{equation} P_w = \sum_{i\ne w,j=1,\ldots,r} X_{ij} \le (n-1) r. \end{equation}

Adding these two inequalities gives \begin{equation} P_1 + P_w \le (n-1) m. \end{equation} This proves the result.

Will Nelson
  • 5,161
1

let $a_{k}$ students answer the $k-th$ problem

$$p_{1}\le\sum_{k=1}^{m}(n-a_{k}),p_{1}+p_{2}+\cdots+p_{n}=\sum_{k=1}^{m}a_{k}(n-a_{k})$$ then \begin{align*} p_{1}+p_{n}\le p_{1}+\dfrac{p_{2}+p_{3}+\cdots+p_{n}}{n-1} &=\dfrac{n-2}{n-1}p_{1}+\dfrac{p_{1}+p_{2}+\cdots+p_{n}}{n-1}\le\dfrac{n-2}{n-1} \sum_{k=1}^{m}(n-a_{k})+\dfrac{1}{n-1}\sum_{k=1}^{m}a_{k}(n-a_{k})\\ &=m(n-1)-\dfrac{1}{n-1}\sum_{k=1}^{m}(1-a_{k})^2\\ &\le m(n-1) \end{align*} because $$\dfrac{n-2}{n-1}[mn-\sum_{k=1}^{m}a_{k}]+\dfrac{n}{n-1}\sum_{k=1}^{m}a_{k}-\dfrac{1}{n-1}\sum_{k=1}^{m}a^2_{k}= m(n-1)-\dfrac{1}{n-1}\sum_{k=1}^{m}(1-a_{k})^2$$ if and only if $$a_{1}=\cdots=a_{m}=1,p_{1}=m(n-1),p_{2}=\cdots=p_{n}=0$$

math110
  • 93,304