Find the maximum the value $P_{1}\cdot P_{n}$

Suppose that $n \ge 2$ students attend a test of $m \ge 2$ problems. The scoring rule for each problem is: if $x$ students answer a problem incorrectly, then a correct answer is worth $x$ points and an incorrect answer is 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}$$ Find the maximum of the value $P_{1}\cdot P_{n}$.

Let $a_{k}$ students answer the $k$-th problem then $$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})$$ so $$p_{1}\cdot p_{n}\le p_{1}\cdot \dfrac{p_{2}+p_{3}+\cdots+p_{n}}{n-1}$$

I use this idea,at last,I can't solve this problem,(But I fell this problem can use this idea)

PS: Somedays ago, I have solve this problem : How find this maximum of $P_{1}+P_{n}$

Solution 1:

Let $x_i$ be the score of the $i$-th problem, then \begin{equation} \begin{split} P_1 &\le \sum_{i=1}^{m} x_i \\ P_n &\le \frac{1}{n-1} \Big( \sum_{i=1}^m x_i (n-x_i) - P_1 \Big) \end{split} \end{equation}

denote $S = \sum_{i=1}^{m} x_i, T = \sum_{i=1}^m x_i (n-x_i)$, $P_1 P_n \le \frac{1}{n-1} P_1 ( T - P_1 )$.

In case $T \ge 2S$, \begin{equation} \begin{split} P_1 P_n &\le \frac{1}{n-1} S(T-S) \\ & = \frac{1}{n-1} S\Big((n-1)S - \sum x_i^2 \Big) \\ & \le \frac{1}{n-1} S\Big((n-1)S - \frac{S^2}{m} \Big) \\ & = 4m^2(n-1)^2 \cdot \frac{S}{2m(n-1)} \cdot \frac{S}{2m(n-1)} \Big( 1-\frac{S}{m(n-1)} \Big) \\ & \le \frac{4}{27} m^2(n-1)^2. \end{split} \end{equation} The strategy to this bound is: $P_1$ get every problem correct, others try to have equal total score, and every problem has score $\frac{2}{3}(n-1)$. If $n \equiv 1$ (mod $3$), this bound can be achieved, slightly less for other $n$. But to make $T \ge 2S$ possible, we need $n \ge 4$.

In case $T \le 2S$, \begin{equation} \begin{split} P_1 P_n &\le \frac{1}{n-1} \cdot \frac{T^2}{4} \le \frac{1}{n-1} S^2 \le m^2(n-1). \end{split} \end{equation} This is just a rough estimation we can't take equality, but proves for $n \ge 8$, previous strategy is the best.

Actually in case $T \le 2S$, we have $T \le 2m(n-2)$. (for $n \ge 3$)

Rewrite the condition $T \le 2S$ as \begin{equation} \sum_{i=2}^{n-1} (i-2)(n-i) \#_i \le (n-1) \#_1 \end{equation} where $\#_i$ is number of $x_j$ equal to $n-i$. One can check \begin{equation} \frac{(i-2)(n-i)}{n-1} \ge \frac{i(n-i)-2(n-2)}{n-3}. \end{equation} Hence \begin{equation} \sum_{i=3}^{n-1} i(n-i)-2(n-2) \#_i \le (n-3) \#_1, \\ \sum_{i=1}^{n-1} i(n-i) \#_i \le \sum_i 2(n-2) \#_i, \end{equation} this is exactly what we want.

This gives a new bound $\frac{m^2(n-2)^2}{n-1}$, can be achieved by taking $x_i = n-2$ for any $i$. This is the previous bound for $n=4$, for $n=5,6,7$, previous bound is larger, for large $m$ previous bound is better, for small $m$, you probably need to compare. For $n=3$, result is $\frac{m^2}{2}$.

For n = 2, result is $\frac{m^2}{4}$.

Solution 2:

Here's a thought experiment. Let us say we communicated to the students that they all get an A grade if they get the max score $P_1 \times P_n$. Let us also assume that all students know answers to all the questions that may be asked. They meet together and come up with the following scheme to maximize the group score $P_1 \times P_n$ (illustrated for $n = 6$ students and $m = 4$ tests):

The scheme works like this. One student called the lead, student #6 in this case, is chosen to answer all tests correctly. The other students will answer tests in a predetermined manner (highlighted in the yellow cells) after choosing one test that is reserved for the lead. We call this reserved test as the ace test, test#1 in this case. Note that if even a single student does not answer at least one test correctly, then $P_1$ will become zero. There has to be one ace test so that we can get maximize $P_n$. Note that $P_n$ is maximized when only one student gets the test right and others get it wrong. The lead taking the ace test correctly ensures this.

The maximal $P_n = n$.

Here's what happens if the other students all answer the same test correctly:

Here's what happens if the staggering of the non-ace tests among the non-lead students is not done without 'distributing' the tests amongst them. For optimal scores, the distribution can be done in any round-robin fashion.

So, we observe that any distribution of the tests amongst the non-lead students other than the staggering we showed here results in reducing $P_1$ from the optimal value that can be attained. We can calculate $P_1$ as follows:

The maximum number of tests answered correctly by a non-lead is given by

$$T_{max} = \lfloor { {n-1} \over (m-1) } \rfloor$$

So, maximal $P_1$ is given by

$$P_1 = P_n - T_{max} = n - \lfloor { {n-1} \over (m-1) } \rfloor$$

Maximal $P_1 \times P_n$ is given by

$$n(n - \lfloor { {n-1} \over (m-1) } \rfloor)$$

This is still a conjecture and not a proof. In order to prove that the above method gives the maximal $P_1 \times P_n$, some more work is needed:

Subproblem: Prove that any other strategy achieves suboptimal $P_1 \times P_n$

Given the configuration of the assignments as described above (in the first picture), we will now attempt the following operations to achieve a score that is higher than what has been achieved.

(a) Change any non-lead's $1$ to $0$:

This causes $P_1$ to drop to 0 and hence $P_1 \times P_n$ becomes 0, suboptimal.

(b) Change any non-lead's $0$ to $1$:

This causes $P_n$ to reduce by 1 and hence $P_1 \times P_n$ is reduced by $P_1$, suboptimal.

(c) Change the lead $1$ to $0$:

This reduces $P_n$ by 1 and hence suboptimal.

Since any change from current configuration results in suboptimal $P_1 \times P_n$ the assignment we have must be optimal.

QED