Mathematics Exam

For any question, if there are 12 or more people choosing the same option, then by the pigeonhole principle, at least 2 of these people must have the same answer to another question as well (since each question only has 11 options). These 2 people will thus have at least 2 answers in common, contradicting the condition in the question. Hence, there are at most 11 people choosing the same option for each question.

In addition, for any question, there are 11 options chosen by 111 students. By the pigeonhole principle, at least one option must be chosen by at least 11 students (since $11 \times 10 = 110 < 111$ ). We have established above that each option is chosen by a maximum of 11 students, so for every question, there must be at least one option that is chosen by exactly 11 students, with no other options being chosen by greater than 11 students. Thus, the option that is chosen the most number of times will have been chosen by exactly 11 students.

The total scores of the students for each of the 11 questions will sum up to the total score of the students for the entire paper. The answer to each of the 11 questions will only affect the total score of the students for that question and no other questions (i.e. they are independent), so this means that we can consider the questions separately and try to maximise the total score of the students for each of the questions. To do this, we just let the option that is chosen the most number of times for each question be the right answer for that question. This will mean that exactly 11 students answered each question correctly, so the maximum total score will be $11 \times 11 = 121$ .

Therefore, the highest possible average mark for the students is $\frac{121}{111}$ , and the answer we want is $121+111=232$ .

Each question can be answered correctly on at most $11$ papers. This is because any two students who answer it correctly cannot have the same answers for any other given question, and that other question can have at most $11$ different answers. So the maximum total number of correct answers on all the papers is $11 \cdot 11$ , which would give an average score of $11 \cdot 11 / 111 = 121 / 111$ .

To show that this maximum average is attained, we exhibit a collection of papers that satisfies the condition. Label each student with an ordered pair $(a,b)$ in ${\mathbb F}_{11}^2$ , where ${\mathbb F}_{11}$ is the field with $11$ elements (the integers mod $11$ ). Label the questions $0, 1, \ldots, 10$ and the answers $0, 1, \ldots, 10$ . Now we mandate that student $(a,b)$ answers question $x$ with the answer $ax+b \in {\mathbb F}_{11}$ . Note that if $a_1 x + b_1 = a_2 x + b_2$ , then $x$ is determined uniquely as $x = (b_2-b_1)/(a_1-a_2)$ , and this expression makes sense unless $a_1 = a_2$ , but in that case $b_1 = b_2$ and they are the same student. So the point is that each distinct pair of students have at most one answer in common.

Let's further stipulate that the $111$ students are made up of the $110$ ordered pairs $(a,b)$ with $a \ne 0$ , plus the ordered pair $(0,0)$ . And let's also stipulate that the correct answer to every question is $0$ . Then the first $110$ students all have exactly one correct answer: student $(a,b)$ gets question $-b/a$ right. And student $(0,0)$ gets a perfect score. That adds up to $110 + 11 = 121$ correct answers, which we already saw is the maximum.

So the answer is $121 + 111 = \fbox{232}$ .

When I first saw this question, there was no hint on how to begin. So I decided to just analyse what I was given and try to formulate some observations or lemmas as I will call them. A quick skim through the question show that:

no two students have more than one answer in common

seems quite fishy, in a sense that this suggests $2$ approaches: pigeonhole and double counting. It turns out that the former works. Let us rephrase this into a lemma.

Lemma 1 : For each option of each question, there are at most $11$ people choosing that option.

Proof: Consider to the contrary. Suppose for a certain question, $≥ 12$ people chose the same option. By the pigeonhole principle, we have $≥ 2$ people who will have chosen the same answer to another question since there are only $11$ possible choices for the questions. This clearly violates the condition that no two students have more than one answer in common. □

---

Now having sorted out the phrasing of the problem, I turned to the numerical values provided. I asked myself, what is the correlation between $111$ and $11$ ? (This is a common tactic in problem solving, normally the values are chosen specially for a specific function, understanding why the variables are chosen helps us to select a proper approach.) Tinkering a bit, it dawned upon me that $111 > 110 = 10 \times 11$ whence the implication of pigeonhole. This provides some insight as to how many students chose a particular option. Another motivation for the following lemma is by drawing out an "adjacency matrix" (at least that's what my trainers refer to), as in a matrix where $a_{ij} = 0,1$ . We would love to count the number of $1s$ hence the inspiration.

Lemma 2 : For a particular question, the maximum number of students that choose a particular option is $11$ .

Proof: We start off with the observation that $11 \times 10 < 111$ , so for each question. Once this is established, pigeonhole gives us that for any question, at least one option must have been chosen by $≥ 11$ students. By Lemma $1$ , however, each option of each question is chosen by at most $11$ students. These two inequalities combined gives that there has to be an option that is chosen by exactly $11$ students, whence the statement in the lemma. □

Notice the usefulness in proving $n ≥ a$ and then $n ≤ a$ to establish $n = a$ . This is a common technique when no obvious bijection or correspondence is available.

---

Let us remark that the average mark of the students is in fact:

$\frac{\text{total marks of all of students}}{111} (*)$

Let us treat the numerator as a whole and see the big picture . Instead of treating individual students, let us instead look at individual questions (students' answers are sort of like variables - we try to keep things "constant"). Since the questions themselves are independent by definition, we can maximise the total score of the students by making as many students getting the question correct as possible. In other words, let the option that is chosen the most be the correct answer.

Well, by Lemma $2$ and the above observation, exactly $11$ students answered each of the $11$ question correctly. Which means that the highest possible average mark (by subbing into $(*)$ ) is $\frac{a}{b} = \frac{ 11 \times 11}{111} = \frac{121}{111} ⇔ a + b = 121 + 111 = \fbox{232}$ .

If no two students can have more than one answer in common, then the best case scenario would be when they all have 1 correct answer in common. This means the total they would score is: $111 \times 1 = 111$ But one of the students could have full marks making the maximum total of the marks $111 + 10 = 121$ (as that student would score 10 more than everyone else). The average score for the students would then be $\frac{121}{111}$ and so $a + b = 111+121 = \boxed{232}$

We prove that an optimal solution exists in which one of the students get a perfect score of 11, and all other students get a score of 1. The average mark in this case is $(111 + 10) / 111 = 232/111$ .

First we show that there is no solution with a higher average mark. Suppose we know the answers of all students but the last in an optimal solution, and we want to assign correct answers, as well as the last student's answers, such that the average mark is maximized. In other words, we want to maximize the total number of student-problem pairs $s, p$ such that $s$ correctly answers $p$ . This quantity can be split into the sum of 11 separate numbers, one for each problem $p$ . So the best we can do is, for each problem $p$ , pick the most common answer among the first 110 students (if there are two answers appearing 55 times each, either will do). This fixes the number of correct answers for problem $p$ involving the first 110 students. To maximize the number of correct answers including the last student, we can make him get a perfect score. Therefore there is an optimal solution in which a student gets a perfect score. Then the score of all other students is at most 1 since they only agree with him on at most one problem.

Next we show that this average mark can indeed be achieved by constructing an explicit solution. For this we use arithmetic over the finite field ${\mathbb F}_{11}$ , i.e., arithmetic modulo the prime 11. The idea is that two different degree-1 polynomials over any field can only agree at one point, just like the students' answers to the problems. (In fact, the same idea is the basis behind the Reed-Solomon error-correcting code that is used, e.g., in CDs.)

Let $A = \{ (a, b) \in {\mathbb F}_{11} \times {\mathbb F}_{11} \mid (a \neq 0) \vee (a = 0 \wedge b = 0) \}.$

The size of $A$ is $|A| = 11 \cdot 11 - 10 = 111$ . We identify each element of $A$ with one of the students. Also we number problems and answers from 0 to 10 inclusive (again, the elements of ${\mathbb F}_{11}$ ). The answer that student $(a, b)$ gives to problem $x$ is given in our construction by $(a\cdot x + b) \bmod 11$ . The correct answer for every problem is answer number 0.

So far we have 111 students, 11 problems, 11 answers per problem and each student marks an answer for each problem. Note that student $(0, 0)$ gets a perfect score. Also, for any $a_2 \neq 0$ there is only one solution $x = -b/a_2 \pmod{11}$ to $a_2 \cdot x + b = 0$ , so all other students get a score of 1.

It remains to be shown that no two distinct students $(a_1, b_1)$ and $(a_2, b_2)$ give the same answer for more than one problem. If $a_1$ or $a_2$ are zero, say $a_1 = 0$ (and therefore $b_1=0$ ), then this holds because as we saw, all other students only give the zero answer to one problem. When $a_1$ and $a_2$ are non-zero, the claim follows because $$a 1 \cdot x + b 1 \equiv a 2 \cdot x + b 2 \pmod {11}$$ implies $$(a 1 - a 2) x = b 2 - b 1.$$ If we also had $(a_1 - a_2) y = b_2 - b_1$ for some $y \neq x$ , then we would get $(a_1 - a_2) (x - y) = 0$ . Dividing (modulo 11) by the non-zero element $x - y$ , we conclude that $a_1 = a_2$ , so $0 = b_2 - b_1$ and $b_1 = b_2$ as well. This means thay are the same student, as we wished to show.

if 1 student achieves full marks (11) then the maximum the other students can achieve is 1 mark: 1x11 + 110x1=121 average: 121/111 and 121+111=232 Alternatively All the students can have one question correct ( the first one for example) (1x111) and ten students can have another one question correct (1x10).