Optimise The Students

This is a construction problem.

---

As with most such questions, the idea for finding the bound is to use pigeonhole principle . There are $7$ different scores for each question. We notice that if $n \geq 50$ then at least $\lceil \frac{50}{7} \rceil = 8$ candidates had the same score on a question, WLOG it is question $1$ . Then since $8 > 7$ by pigeonhole principle at least $2$ students would have the same score on another question, say question $2$ . This contradicts our hypothesis.

---

Now, for the construction. How I thought about this was to let the score of each student be a function , say $f$ from the interval $\lbrack 1,5 \rbrack$ to $\lbrack 1,7 \rbrack$ . So we need to come up with a (really big) family of functions that satisfy the condition that: no two functions evaluate to the same value at more than one point . Well consider two lines . Clearly they can intersect at at most one point! This motivates us to write $\ \text{Score of a student} = \alpha \times \text{Problem Number} + \beta$ . The other idea here is that integers $\pmod{7}$ behave very much like real numbers themselves! So our intuitive line intersection thingy actually works.

---

Enough of motivation, let us move on to the construction itself:

Now for any $1 \leq x,y,z \leq 7$ , let $a_{x,y,z}$ be the integer in $\{1, 2, \ldots, 7 \}$ that is congruent to $x+yz \pmod{7}$ . Consider $49$ contestants $q_{x,y}$ where contestant $q_{xy}$ receives score $a_{x,y,z}$ on question $z$ . Suppose two contestants $q_{x_1,y_1}$ and $q_{x_2,y_2}$ had the same score on two distinct questions $z_1$ and $z_2$ . This means that $(x_1 - x_2) + (y_1 - y_2)z_1 \equiv (x_1 - x_2) + (y_1 - y_2)z_2 \equiv 0 \pmod{7}$ . Subtracting and rearranging we get, $(y_1 - y_2)(z_1 - z_2) \equiv 0 \pmod{7} \Rightarrow y_1 \equiv y_2 \pmod{7} \Rightarrow y_1 = y_2$ . This immediately implies that $x_1 = x_2$ which is a contradiction. □

For the first question, a candidate could get any score from 1-7. For each of those scores, you can show that at most 7 people could have gotten the rest of the questions with different scores from anyone else. All that remains is to show that it exists, and no two people have any 2 other questions with the same score.

You can change the "rotation" of the scores to a different amount to make everything symmetrical and prevent two people from having the same score on two different questions. For everyone who got 7 on the first question, the scores on the rest of their questions would be: 7777, 6666, 5555, 4444, 3333, 2222, 1111

This has a rotation of 0.

For everyone who got a 6 on the first question, you can change the rotation to 1 which would give the following: 7654, 6543, 5432, 4321, 3217, 2176, 1765

You can check that this works by taking any question from 2-5 and checking for any score if the rest of the scores are different for each question. For this example, I'll just list out all scores of 1 on the second question. 71111, 61765, 51642, 41527, 31473, 21357, 11234

You can see how each digit rotates for every score with a 1 on the second question.

Therefore, the answer is $7\cdot 7 = \boxed{49}$

Very similar to the following question: https://brilliant.org/community-problem/safecracking/?group=XOjoLDJnp6JP&ref_id=106803

The 49-bound works nice since 7 is a prime and two straight lines in $\mathbb{F}_7^2$ cannot intersect in more than one point, as usual. Hence if we have a question score in $[1,p]$ and less than $p$ questions, with $p$ being a prime number, the optimal $p^2$ bound still holds. Now I wonder: what happens if we have fewer than $n$ questions with a question score in $[1,n]$ , but $n$ is not a prime number? I am expecting a $\gg n^2$ -bound, but how much $n^2$ is far from the truth? The problem gets more exciting by replacing 7 with 8 (or just introducing the zero score), for instance.

It looked like a pigeon-hole problem. But I could not find out the appropriate pigeon holes and the pigeons. So I tried to solve it in an un-intelligent way. If we write scores in 5 questions for the candidates as 11111 upto 77777 then there are 7^5 combinations. Applying the constraints as any 2 digits will not be same in 2 combinations, it will run as 11111, 12345, 13254,... It will count upto 49.

Pidgeonhole! Let the boxes be a set of 2 of the problems. For each candidate, they have a ball associated with those 2 questions. For example, if a participant had 1 point in P1, 7 in the rest then the ball that would go into the P1&P2 box would be (1, 7). We want for all the balls in each box, that they are all distinct. At most, we can have (1,1) appear (meaning that he got 1 point for both 2 problems of that box) to (7,7). There are 7 ways for each of the 2 numbers so the answer is 49.