Hiho! Let n be the number of participant with n=5k+r, r\in\{0,1,2,3,4\}. Then, let a_i\in\{0,1,2,3,4,5,6\}, i=1,2,...,n be the number of problems solved by the participant i. Further, let x be the number of triples (i,j,k), for which the ikth participant has solved the i-th and j-th problem. [EDITED] Then, by assumption, we get x\geq{6\choose 2}\lceil\frac{2n}{5}\rceil if n is not divisible by 5 or x\geq{6\choose 2}\left(\frac{2n}{5}+1\right) if n is. On the other hand, we get the exact value by \sum {a_i\choose 2}. Assuming that at most one particpant has solved 5 problems, we get x\leq (n-1){4\choose 2}+{5\choose 2}=6n+4=30k+6r+4. If r=0,1,2, we have x\geq {6\choose 2}(2k+1)=30k+15 , whence 6r\geq 11, which is a contradiction if r\neq 2. If r=3,4, we have x\geq {6\choose 2 }(2k+2)=30k+30, whence 6r\geq 26, which is a contradiction. So what's left is the case when n\equiv 2\pmod{5}. Perhaps somebody finds a nice conclusion of this proof. Hanno

Maybe I made some stupid mistake, but it seems to be straightforward. Wlog, we assume that, say, Fedja solved problems 1,2,3,4,5 and other $N$ participants have solved 4 problems each (if not, we tell to some of them solutions of some problems which they did not going to solve for satisfying this condition). For any two indecies $1\le i<j\le 6$ we know that the total number of participants who has solved problems $i$ and $j$ is not less than $(2N+3)/5$ (since it is integral and is more than $2(N+1)/5$). Sum up by all 15 pairs of indecies. Fedja will be counted 10 times, each other will be counted 6 times. So, we get $6N+10\ge 3(2N+3)=6N+9$. It is right inequality indeed, but the difference between LHS and RHS is exactly 1. It means that 1) $2N+3$ is divisible by 5. Indeed, if not, we have $\ge (2N+4)/5$ instead $(2N+3)/5$ in our estimates, and ge wrong inequality $6N+10\ge 3(2n+4)$. 2) for all pairs of problems except 1 the number of participants which solved both problems from this pair is exactly $k=(2N+3)/5$, while for one pair of problems this number equals $k+1$. There are two principal cases: this exceptional pair contains problem 6 or not. a) exceptional pair contains problem 6, say, it is 61. Sum up numbers of participants, which solved 61,62,63,64,65. Every counted participant was counted 3 times, hence $5k+1$ is divisible by 3. On the other hand, sum up numbers of participants, which solved 12,13,14,15,16. Fedja will be counted 4 times, each other 3 times, hence $5k+1$ is congruent to 4 modulo 3. A contradiction. a) exceptional pair does not contain problem 6, say, it is 34. Do the same thing, just with $5k$ instead $5k+1$.

I think this problem appears in IMO 1998 problem 2, exactly the same problem. IMO 2005 is too easy, I'm sure more than 60 contestants score 42 points, China, Russia, USA, Bulgaria, Vietnam, Korea score a total of 252 points.

mozilla wrote: I think this problem appears in IMO 1998 problem 2, exactly the same problem. IMO 2005 is too easy, I'm sure more than 60 contestants score 42 points, China, Russia, USA, Bulgaria, Vietnam, Korea score a total of 252 points. An interesting prognose.. Imo 1998 problem 2: In a competition there are a contestants and b judges, where $b\geq3$ is an odd integer. Each judge rates each contestant as either “pass” or “fail”. Suppose k is a number such that for any two judges their ratings coincide for at most k contestants. Prove $\frac{k}{a}\geq \frac{b-1}{2b}$.

I agree with the IMO 98 #2 observation. When I did this problem, I initially approached it using the techniques I remembered from that problem (basically counting in two ways), and it just fell right out. In fact, while $n \equiv 2 {\pmod 5}$ is the only case we have to deal with (where n is the number of contestants), it doesn't even really matter. The contradiction from counting in two ways is direct and does not depend on the modular value of n.

(I first thought that a nicer solution could be achived by considering a bip. graph with one partition being the problems and the other the n contestants and then achieve a contradiction like that, but i wasn't lucky that way, so i think it would be the same thing but just reinterpreting the problem in graphs terms) Well, here goes an ungly but a complete and correct ( i hope!) solution: Let $c$ be the number of students who solved at most 4 problems and let $k$ be the number of students who solved exactly 5 and $n=c+k$ the total number of students. A "trio" is a pair of problems and a particular contestant who solved the pair. So we have $ {4\choose 2}c + {5\choose 2}k=6n+4k$ trios. We also know that for each of the 15 pairs we have more than $\frac{2n}{5}$ trios. Case 1 $n=5p$ For each of the 15 pairs we have at least $\frac{2n}{5} +1$ trios. So a total of at least $6n+15$ pairs so from this we have $6n+4k \geq 6n+15$ so $k \geq 4$ Case 2$n=5p+1$ Doing the same thing as in case 1 we obtain $k \geq 3$ Case 3 $n=5p+3$ Doing the same thing as in cases 1 and 2 we obtain $k \geq 3$ Case 4 $n=5p+4$ Doing the same as in the above cases we obtain $k \geq 2$ Case 5$n=5p+2$ Doing the same as in the above cases we obtain $k \geq 1$ but we have to show that $k \geq 2$ So suppose not, that is there are $5p+1=c$ contestants with at most 4 solved problems and $k=1$ that solved exactly 5 problems.WLOG assume each of the $c$ contestans solved 4 problems. Let 1,2,3,4,5,6 be the 6 different problems. WLOG assume that the contestant who solved 5 problems, solved problems 1,2,3,4,5. The total number of trios is $6(5p+1)+10=30p +16$ For each pair of problems the number of trios is at least $\lceil \frac{2n}{5} \rceil = 2p+1$. So we have 14 pairs with $2p+1$ trios and one pair with $2p+2$ . Now lets count for every problems the numbers of trios in which that problem is included. For 4 of the problems, this number must be $5(2p+1) = 10p+5$. For 2 of the problems this number must be $4(2p+1)+(2p+2) = 10p+6$ Let $a_1,...,a_n$ be the contestants. If we start with the contestant $a_m$ who has solved the 5 problems 1,2,3,4,5, the number of triosper problem is given by the following table: problem:.1 - 2 - 3 - 4 - 5 - 6 - - - - - - - - - - - - - - - - - - - - - - - - - - - trios $a_m$ : 4 - 4 - 4 - 4 - 4 - 0 ......... $a_j$: 3 - 3 - 3 - 3 - 0 - 0 Now imagine that we add the contestants that have solved 4 problems, one by one. Each contestant will increase the number of trios for each of the problems he has solved by 3, whilst the number of trios for the two problems he has not solved stays the same. In the end, the table must have 4 columns with each summing to a value $10p+5$ and 2 columns each summing to a value $10p+6$. This means that among the first five columns, there must be one with entries summing to $10p+5$ and one with entrie summing to $10p+6$. However, the value of each of the first 5 columns is of the form $4+3i$ for some $i$, hence it is impossible that two of the first 5 columns differ only by 1 in the end. Therefore, our assumption that such a counterexample exists must have been wrong. This shows that $k \geq 2$ must hold also for $n=5p+2$

Here's my partial solution: Let there be $n$ students. Make a grid with $n$ rows and 15 columns. Each column represents a PAIR of problems, and each row represents a student. Mark a square if the student for its row solved the pair of problems for its column. Since the number of marked squares in each row is at least $\frac{2}{5}n+\frac{1}{5}$, the total number of marked squares in the grid is at least $\frac{2}{5}$ of the total number of squares plus three more--that is, at least $6n+3$. Now look at each row. If a student solves 4 problems, he/she solves 6 pairs. If a student solves 5 problems, he/she solves 10 pairs. If at most one student solves 5 problems, then the maximal number of marked squares is $6n+4$. I think from here a contradiction can probably be derived, but I don't know how yet.

Ofcourse, the idea of the solution it is preaty obvious... but why don't you all write a clear solution ? I'll write mine and i hope that i'm right. Let $n$ be the number of the contestants and $a_n$ the problems the $n$th contestant solved. Then, by counting the number of triples (problem,problem,contestant) such that both two problems were solved by the contestant, we easily get that $6n=\frac{2}{5} \cdot n \cdot {6\choose 2} < \sum_{i=1}^n \frac{a_i \cdot (a_i -1)}{2} $. If noone solved 5 problems, then $a_i \leq 4$ for all $i$. So $6n < \sum_{i=1}^n \frac{a_i \cdot (a_i -1)}{2} \leq \sum_{i=1}^n 2 \cdot (a_i -1)$. But since both sides are even we get : $ 6n +2 \leq \sum_{i=1}^n 2 \cdot (a_i -1)$ or $ 4n +1 \leq \sum_{i=1}^n a_i \leq 4n $ . Contradiction. If only one solved 5, let her be $a_n$. Then, similarly, $6n +1 \leq 5+ \sum_{i=1}^{n-1} \frac{a_i \cdot (a_i -1)}{2} \leq 5+ \frac{3}{2} \cdot \sum_{i=1}^{n-1} (a_i) \leq 5 + \frac{3}{2} \cdot 4 \cdot (n-1)$ so $ 6n +1 \leq 6n -1$. Contradiction. The result follows.

Anto, your solution is wrong, because $a(a-1)/2$ for $a=5$ equals 10, not 5.

Ofcourse it is! What a stupidity! It couldn't be that simple! Althgought it's not that hard either. Anyway, I know how to fix the gap, but i'm not posting it, because it is similar to manuel's approach, so no reason for writting it. Thanks, Fedor.

Hola! I am in Merida, Mexico now. I would just like to say that showing that n is congruent to 2 mod 5 is not worth anything. I thought it should have been worth something, but... In any case, once you get this part the IOs come naturally, so you could say it IS worth something, if you just mention a few more things. But not worth a lot in total anyway. Singapore has coordinated 3 Qs so far, and we tried to get 6 done, but apparently they are still scrutinising our scripts, so I am free till after lunch. *grumble* Rats. I cannot type well on this keyboard. For one I cannot find the apostrophe key. Well, I believe that Singapore can get more points for Q6 than for Q1, which is really strange! In fact, Q1 is probably our HARDEST problem. 4 is the easiest, followed by Q3, for us. Ugh. This is a really strange IMO for us. Well, we all have Chichen Itza to look forward to tomorrow, barring hurricanes. That is, Hurricane Emily.

Um, okay, some last thoughts. After obtaining the congruent to 2 mod 5 thing, I do a contradiction argument. I consider the special column that the 5-problems solver did not solve, and count problem pairs. That gets rid of one case. Then I consider the column with the least solutions, then count pairs again. This finishes the other case. This is the approach one of our contestants used, so I am going to try to push for more marks. He used the same approach as I did, but stops 2-3 lines short of the solution. What a pity. And those 2-3 lines are not even difficult. I have it written down in my notes and I hope the coordinators will agree it is easy to complete when they see what he has done.

Hi once again! Quote: Let n be the number of participant with n=5k+r, r\in\{0,1,2,3,4\}. Then, let a_i\in\{0,1,2,3,4,5,6\}, i=1,2,...,n be the number of problems solved by the participant i. Further, let x be the number of triples (i,j,k), for which the ikth participant has solved the i-th and j-th problem. [EDITED] Then, by assumption, we get x\geq{6\choose 2}\lceil\frac{2n}{5}\rceil if n is not divisible by 5 or x\geq{6\choose 2}\left(\frac{2n}{5}+1\right) if n is. On the other hand, we get the exact value by \sum {a_i\choose 2}. Assuming that at most one particpant has solved 5 problems, we get x\leq (n-1){4\choose 2}+{5\choose 2}=6n+10=30k+6r+4. If r=0,1,2, we have x\geq {6\choose 2}(2k+1)=30k+15 , whence 6r\geq 11, which is a contradiction if r\neq 2. If r=3,4, we have x\geq {6\choose 2 }(2k+2)=30k+30, whence 6r\geq 26, which is a contradiction. So what's left is the case when n\equiv 2\pmod{5}. Perhaps somebody finds a nice conclusion of this proof. Let's check when the case n\equiv 2\pmod {5} does not lead immediately to a contradiction. In fact, if our inequalities become equalities, that is, if {4\choose 2}(n-1)+{5\choose 2}={6\choose 2}\frac{2(n+3)}{5}. But this is a contradiction since the LHS is congruent to 1 modulo 5 and the RHS is congruent to 0 mod 5. But, if we want to change the estimation on the LHS, we have to replace one of the binomial coefficients by a lower value; but, whatever we do, we get LHS which is at least 2 smaller as the old one, which leads to a contradiction since we must have 6r\geq 11. On the other side, we can assume that the RHS is 1 bigger than the old one - then we get {4\choose 2}(n-1)+{5\choose 2}={6\choose 2}\frac{2(n+3)}{5}+1, which is also a contradiction since the LHS is congruent to 4 modulo 6 and the RHS is congruent to 1 modulo 6. Other cases cannot occur and we're done. Hanno

Hanno wrote: In fact, if our inequalities become equalities, that is, if {4\choose 2}(n-1)+{5\choose 2}={6\choose 2}\frac{2(n+3)}{5}. Hi, this is wrong. It should be $\binom{4}{2}(n-1)+\binom{5}{2} \geq \binom{6}{2}\frac{2n+1}{5}$. By the way Fedor Petrov already proved the case for $n\equiv 2 \pmod{5}$, he assumes that one contestant solves 1,2,3,4,5. Then he counts: 1) number of contestants who solve 16,26,36,46,56 2) number of contestants who solve 16,15,14,13,12. These two countings have equal values but they are different mod 3, contradiction.

Hi! Thanks, what a stupid mistake. Hanno

Hello, I'm not sure I should ask this question here. If so, I apologies. I don't quite understand [every two of these problems were solved by more than 2/3 of the contestants] We have; Problem 1 2 3 4 5 6 So does that mean, if n = contestants 1 was solved by >=2n/3 3 || 5 || ? Or does it mean: 1 och 2 was solved by >=2n/3 3 och 4 was solved by >=2n/3 ... ? Because if it is the first argument then there's nothing stopping everyone from getting 0 points on problem 2, 4 and 6? (I never do problems (nor math ) so yes, I'm stupid)

Hanno wrote: So what's left is the case when n\equiv 2\pmod{5}. Perhaps somebody finds a nice conclusion of this proof. Here it goes, simple and short (if you find a hole let me know): Let's suppose the contrary- there was at most one student who solved 5 problems. Then the number A:=x is at most 6n+4, where the maximum is achieved when 1 student solved 5 problems (10 pairs), and all the other- only four (6 pairs). In the case n=5k+2, each pair of problems was solved by at least \displaystyle \lceil2k+\frac{4}{5}\rceil =2k+1 students. Note that a)If at least 1 pair was solved by 2k+3 students, then B:=x is at least 30k+17=6n+5. b)If at least 2 pairs were solved by 2k+2 students, then B is at least 30k+17=6n+5. Anyway, x=A<B=x in contradiction. Then at most one pair was solved by 2k+2 students, and all the other were solved by 2k+1. In the first case A=6n+4=15(2k+1)=B. Contradiction (parity). In the second case A=6n+4= 14(2k+1)+2k+2=B, which reduces to n=5k+4. Contradiction. Therefore we're done.

mozilla wrote: Hanno wrote: In fact, if our inequalities become equalities, that is, if {4\choose 2}(n-1)+{5\choose 2}={6\choose 2}\frac{2(n+3)}{5}. Hi, this is wrong. It should be $\binom{4}{2}(n-1)+\binom{5}{2} \geq \binom{6}{2}\frac{2n+1}{5}$. By the way Fedor Petrov already proved the case for $n\equiv 2 \pmod{5}$, he assumes that one contestant solves 1,2,3,4,5. Then he counts: 1) number of contestants who solve 16,26,36,46,56 2) number of contestants who solve 16,15,14,13,12. These two countings have equal values but they are different mod 3, contradiction. This is not enough. If you look at his proof, he considers two cases, either the 'exceptional pair' is 16 (involving 6) or the exceptional pair is, say, 34 (not involving 6). This is where you show that the values are indeed equal. One of our contestants had about the same solution.

i think the problem means that each pair of problems was solved by > 2/5 of people COMBINED. if each pair was solved by each of these people - each of these people solves 6 problems - which is not true. my proof. let MinActualTotal = actual minimum total of number of problems solved by all people there are 15 distinct pairs of prolems[duplicates and ordering not counted] so MinActualTotal = 30. MinPeople = min number of people = MinActualTotal/5 = 6. this is because each person solves at most 5 problems. let x = number of people solve 5 problems, n = number of people, MaxTotal = max total number of probems solvedn by n people. then MaxTotal = 5x + (n-x)4. if n = MinPeople, then MaxTotal = 5x + (6-x)4 MaxTotal certainly needs to be >= MinActualTotal. That is 5x + (6-x)4 >= 30. So x >=2.

Let's just bash this. Assume otherwise. We introduce some notations : Let the contestants be $C_1,C_2,\dots,C_n$. Let the problems be $P_1,P_2,\dots,P_6$. Let $a_i$ denote the number of problems solved by $C_i$. Let $b_i$ denote the number of contestants who solved $P_i$ Let $x_{ij}$ denote the number of contestants who solved both $P_i$ and $P_j$. By assumption, we have $x_{ij}\geq \frac {2n+1}{5}$. Wlog we have $a_1\leq 5$ and $4\geq a_2\geq a_3\geq \dots \geq a_n$. Let $S$ denote the number of triples $(C_i,P_j,P_k)$ such that $C_i$ solved both $P_i,P_j$. On one hand we have : $$\vert S \vert = \sum_{1\leq i <j \leq 6}x_{ij} \geq \binom 62 \cdot \frac {2n+1}{5} = 6n+3$$We also have : $$\vert S \vert = \sum_{1\leq i \leq n}\binom {a_i}{2} $$ Assume $a_1<5$ , then we have from the above expression : $$\vert S \vert = \sum_{1\leq i \leq n}\binom {a_i}{2} \leq \binom 42 \cdot n =6n<6n+3 $$So $a_1=5$. Next suppose, $a_n<4$. Then we have : $$\vert S \vert = \sum_{1\leq i \leq n}\binom {a_i}{2}\leq 5+\tbinom 42 \cdot (n-2)+ 3=6n+1<6n+3$$ Hence we conclude that $a_1=5$ and $4=a_2=a_3=\cdots a_n$. WLOG , $C_1$ doesnt solve $P6$. Next note that we have : $$\sum_{i=1}^{6}b_i = \sum_{j=1} a_j = 5+4(n-1)=4n+1$$ We will now consider the sum : $$\sum_{j=2}^{6} x_{1j} \geq 5\cdot \frac {2n+1}5=2n+1$$ Note that since every contestant except $C_1$ solving $P_1$ also solves exactly three other problems whereas $P_1$ solves $4$ other problems. This gives : $$\sum_{j=2}^{6} x_{1j}=4+3(b_i-1)=3b_i+1\geq 2n+1$$ This gives $b_i \geq \frac {2n}3$ for all $1\leq i\leq5$. We also have in a similar way : $$\sum_{j=1}^{5} x_{6j}=3b_6\geq 2n+1$$ Assume $n\neq 0\pmod 3$. Then we have $b_i\geq \frac {2n+1}3$ for all $1\leq i\leq5$. So $\displaystyle \sum_{i=1}^{6}b_i\geq 6\cdot \frac {2n+1}3 = 4n+2 (\rightarrow \leftarrow)$. Thus we have $3\mid n \implies b_6 \geq \frac {2n}3+1$. Now we have $\displaystyle \sum_{i=1}^{6}b_i\geq 5\cdot \frac {2n}3+ \frac {2n}3+1 = 4n+1$ Thus since equality holds everywhere, we must have : $b_i=\frac {2n}3$ for all $1\leq i\leq5$ and $b_6=\frac {2n}3+1$. We will now compute $\displaystyle \sum_{1\leq i<j\leq 5}x_{ij}$. Note that it is atleast $\tbinom 52 \cdot \tfrac {2n+1}5=4n+2$. We will count it in another way. Note that $C_1$ solves everything, so he contributes a total of $\tbinom 52$ to the score. The contestants who solved $P6$ solve some $3$ other problems amongst the first five and the contestants who are not $C_1$ and didnt solve $P_6$ solve $4$ amongst the first five problems. So we have : $$\sum_{1\leq i<j\leq 5}x_{ij}= \binom 52 + \binom 42 \cdot (n-1-b_6) + \binom 32 \cdot b_6=4n+1<4n+2$$ Hence we have the desired contradiction and we are done. $\blacksquare$. Remark : Unsurprisingly, this just breaks if pushed hard enough. YUH.

Completely agree with @above's remark. Let $n$ be the number of contestants, and suppose $2n\equiv r\pmod{5},$ where $r\in\{0,1,2,3,4\}.$ Let $x_i$ be the number of contestants who solved $i$ problems. Assume, for the sake of contradiction, that $x_5<2.$ Let $N$ the number of unordered triples $(P_1,P_2,C)$ such that contestant $C$ solved problems $P_1$ and $P_2.$ If we fix $C$ and then choose $C_1,C_2,$ it is easy to see that $$N=\binom{2}{2}x_2+\binom{3}{2}x_3+\binom{4}{2}x_4+\binom{5}{2}x_5.$$On the other hand, if we choose $P_1,P_2$ first, then by the given condition, we have $$N\ge \binom{6}{2}\left(\frac{2n-r}{5}+1\right).$$Therefore, $$x_2+3x_3+6x_4+10x_5\ge 6n-3r+15.$$If $x_5=0,$ then the LHS is clearly less than $6n,$ which is impossible. Hence, $x_5=1,$ so $$x_2+3x_3+6x_4+10\ge 6n-3r+15$$$$\iff 3r-15\ge 6x_0+6x_1+5x_2+3x_3-4$$$$\iff r=4,x_0=x_1=x_2=x_3=0.$$Thus, $1$ contestant solved five problems (say $2,3,4,5,6$) and $n-1$ contestants solved four problems. Call the contestants who solved four problems $\emph{average}$ and let $S_{ab}$ with $a<b$ denote the number of average contestants who solved problems $a$ and $b.$ Observe the following: (1) Since $\binom{3}{2}$ and $\binom{4}{2}$ are both divisible by $3,$ we have $3\mid S_{ab}$ for all $a,b.$ (2) By the given condition, $S_{ab}\ge\frac{2n+1}{5}$ if $a=1$ and $S_{ab}\ge\frac{2n-4}{5}$ if $a\ne 1.$ (3) Since $\sum_{1\le a<b\le 6}S_{ab}=\binom{4}{2}(n-1)=6n-6$ and $5(\frac{2n+1}{5})+10(\frac{2n-4}{5})=6n-7,$ equality is achieved in all but one of the above inequalities. Now note that $$\sum_{a=1,2\le b\le 6}S_{ab}\ge 5\left(\frac{2n+1}{5}\right)=2n+1,$$$$\sum_{2\le a<b\le 6}S_{ab}\ge 5\left(\frac{2n-4}{5}\right)=2n-4.$$Therefore, either $2n+2\equiv 2n-4\equiv 0\pmod{3}$ or $2n+1\equiv 2n-3\pmod{3}.$ Since the latter is clearly impossible, we must have $n\equiv 2\pmod{3}.$ But $$S_{12}+S_{23}+S_{24}+S_{25}+S_{26}\ge \frac{2n+1}{5}+4\left(\frac{2n-4}{5}\right)=2n-3\equiv 1\pmod{3}.$$Hence, the sum on the LHS is congruent to either $1$ or $2$ modulo $3,$ contradiction.

A different Solution: Basically, following is the quick outline of solution: Of course, first we assume contrary and by adding solves WLOG assume that $5$ problems were solved by exactly $1$ contestant and other contestants solves $4$ problems each. Then we look at problems which have $\le \left\lfloor \frac{2n}{3} \right\rfloor$ solves and conclude using them (by double counting) that each pair of problems was solved by exactly $\left\lfloor \frac{2n}{5} \right\rfloor + 1$ students. Moreover we get that $n = 15k-3$ for some $k \in \mathbb{N}$. Finally, we just double count the cardinality of set $T := \{(\{P_i,P_j\},C_k): \text{contestant } C_k \text{ solved both the problems } P_i,P_j \}$ in order to get our desired contradiction. Below are the full details: Assume contrary. Suppose there were $n$ contestants $C_1,C_2,\dots,C_n$ and $P_1,P_2,\dots,P_6$ were the six problems. By adding in solves, We may assume WLOG that one contestant solved exactly $5$ problems and all other solved exactly $4$ problems. We will call a problem less solved if it had at most $\left\lfloor \frac{2n}{3} \right\rfloor$ solves. Also, for different problems $p_1,p_2,\dots,p_l$, denote by $f(p_1,p_2,\dots,p_l)$ the number of contestants who solved all the problem $p_1,p_2,\dots,p_l$. Claim(Key Claim): For Any less solved problem $p$, $f(p) = \left\lfloor \frac{2n}{3} \right\rfloor$. Also, for any problem $q \ne p$, $f(p,q)= \left\lfloor \frac{2n}{5} \right\rfloor + 1$. Moreover, $n= 15k-3$ for some $k \in \mathbb{N}$. proof: Let $f(p) = t$. We bound the value $\sum_{q \ne p} f(p,q)$ in two different ways. Because each contestant (other than one who solved $5$ problems) solved $4$ problems each, so $$\sum_{q \ne p} f(p,q) \le 3(t-1) + 4 = 3t+1 \le 3 \cdot \left\lfloor \frac{2n}{3} \right\rfloor + 1 \le 2n+1$$with equality iff $3 \mid n$ and $t = \left\lfloor \frac{2n}{3} \right\rfloor$. Now, since each pair of problems was solved by at least $\left\lfloor \frac{2n}{5} \right\rfloor + 1$ contestants, so $$\sum_{q \ne p} f(p,q) \ge 5 \cdot \left( \left\lfloor \frac{2n}{5} \right\rfloor + 1 \right) \ge 5 \cdot \frac{2n+1}{5} \ge 2n+1$$with equality iff $n \equiv 2 \pmod{5}$ and $f(q,p) = \left\lfloor \frac{2n}{5} \right\rfloor + 1 ~ \forall ~ q \ne p$. This implies our claim as equality must hold everywhere. $\square$ Now, we know that $f(P_i) \ge \left\lfloor \frac{2n}{3} \right\rfloor = 10k-2 ~ \forall ~ i = 1,2,\dots,6$ and $\sum_{i=1}^6 f(P_i) = 60k-11$. It follows that $5$ of the problem were solved by exactly $10k-2$ contestants and the other was solved by $10k-1$ contestants. So there are $5$ less solved problems. So by our claim it follows that $f(P_i,P_j) = \left\lfloor \frac{2n}{5} \right\rfloor + 1 ~ \forall ~ i \ne j$ as at least of the problems $P_i,P_j$ must be less solved. Now consider the set $$T := \{(\{P_i,P_j\},C_k): \text{contestant } C_k \text{ solved both the problems } P_i,P_j \}$$If we fix $\{P_i,P_j\}$, then we get $$|T| = 15 \cdot (6k-1) = 90k - 15$$On the other hand, if we fix $C_k$, then we get $$|T| = \binom{5}{2} + (15k-4) \cdot \binom{4}{2} = 90k - 14$$This gives us a contradiction and hence completes the proof of the problem.

Here's a terrible writeup of a weird solution: Assume FTSOC that there is at most one person who solved $5$ problems. Let $k$ be a person, and let $a$ and $b$ be problems. We count the number of triples $(k,a,b)$ such that $k$ solved both $a$ and $b$. On one hand, the number of triples is bounded above by $\binom{5}{2}+\binom{4}{2}(n-1)=6n+4$. On the other hand, the number of triples is bounded below by $\binom{6}{2}\frac{2n+1}{5}=6n+3$. Thus, the bound is strong enough that we can deduce some equality cases: 1. The number of people is congruent to $2 \pmod{5}$. 2. One person solved $5$ problems and everyone else solved $4$ problems. 3. One pair of problems was solved by exactly $\frac{2n+6}{5}$ people, and the other pairs were solved by exactly $\frac{2n+1}{5}$. Let $S$ be a set of $5$ problems. We count the number of triples $(k,a,b)$ such that $a,b \in S$ and $k$ solved $a$ and $b$. Notice that this number must either be $4n+2$ or $4n+3$ by statement 3. Now, suppose $S$ is the set of the five problems that one person solved. Then, we have that $S \equiv 1 \pmod{3}$ by summing the contributions of each person. Now, suppose $S$ is any other set of size $5$. Then, we have that $S \equiv 0 \pmod{3}$ similarly. Thus, $4n+2 \equiv 0 \pmod{3}$, so $n \equiv 1 \pmod{3}$. Therefore, we have that $\frac{2n+1}{5} \equiv 0 \pmod{3}$. Now, let's count the number of $5$-element sets of problems such that the number of triples is $1 \pmod{3}$. On one hand, we proved that only one set works. On the other hand, the number of solves of each pair of problems is a multiple of $3$ except one pair, so the number of sets is $4$, a contradiction. Thus, we are done.

Case bash We can assume that WLOG one contestant has solved 5 problems, namely problems 1,2,3,4 and 5; and every other student has solved 4 problems. Now I'll prove that this is impossible. Let $A$ be the number of pairs of problems that need to be solved; and $B$ the number of pairs of problems that the students combined have solved. We need to have $B\geq A$ If $n=5k+1$ we have that $A=15(2k+1)=30k+15$ and $B=10+5k.6=30k+10$, impossible. If $n=5k+2$ we have that $A=15(2k+1)=30k+15$ and $B=10+(5k+1).6=30k+16$, which is possible(for now). If $n=5k+3$ we have that $A=15(2k+2)=30k+30$ and $B=10+(5k+2).6=30k+22$, impossible. If $n=5k+4$ we have that $A=15(2k+2)=30k+30$ and $B=10+(5k+3).6=30k+28$, impossible. If $n=5k+5$ we have that $A=15(2k+3)=30k+45$ and $B=10+(5k+4).6=30k+34$, impossible. So we got that $n=5k+2$. Now let's check the possibilities mod 3. If $n=15k+2$ we have that the total number of problems solved is $5+4(15k+1)=60k+9$, thus one problem has been solved by at most $10k+1$ students. This problem is in $5$ problem pairs, which need to be solved at least $5(6k+1)=30k+5$ times, but these problems pair are solved at most $4+3.10k=30k+4$ times by watching all the students who solved this problem, impossible. If $n=15k+7$ we have that the total number of problems solved is $5+4(15k+6)=60k+29$, thus one problem has been solved by at most $10k+4$ students. This problem is in $5$ problem pairs, which need to be solved at least $5(6k+3)=30k+15$ times, but these problems pair are solved at most $4+3.(10k+3)=30k+13$ times by watching all the students who solved this least solved problem, impossible. Now the hardest case, if $n=15k+12$. Problem $6$ is in $5$ problem pairs and each of these pairs is solved by at least$\frac{2}{5} n= 6k+5$ students, thus these $5$ problem pairs need to be solved in total at least $30k+25$ times. Only students with $4$ problems solved have done problem $6$, thus one student can cover at most $3$ of those $30k+25$ problem pairs, i.e we need $10k+9$ students to have solved problem 6. But we see that in the case $n=5k+2$ we have $B-A$ is at most $1$, i.e we could have at most one pair of problems solved more than enough times. But the $10k+9$ students that have solved problem $6$ cover the $5$ problem pairs with problem $6$ $30k+27$ times, but they need to be covered only $30k+25$ times, i.e there are two extra pairs of problems solved, which we can't happen, so there is no solution in this case as well and we get a contradiction!

Is this right? Suppose we have $n$ students, and at most one of them solved (exactly) $5$ problems. We count the number of ways we can assign any student to two problems that they solved. On one hand, counting by students, this quantity is at most $\tbinom{5}{2}+\tbinom{4}{2}(n-1)=6n+4$. Suppose that $n \not \equiv 2 \pmod{5}$, and count the quantity by pairs of problems. Since $\lceil \tfrac{2n}{5} \rceil \geq \tfrac{2n+2}{5}$ in this scenario, it follows that the desired quantity is at least $\tbinom{6}{2}\tfrac{2n+2}{5}=6n+6$: contradiction. Hence $n \equiv 2 \pmod{5}$, so let $n=5a+2$. In this case, the desired quantity is at least $\tbinom{6}{2}\tfrac{2n+1}{5}=6n+3$, so it must be in $\{6n+3,6n+4\}$. However, note that There must be at least one student who solved exactly $5$ problems, else the quantity is at most $6n$, so there is exactly one student who solved exactly $5$ problems. If at least one student solved less than $4$ problems, the quantity is at most $\tbinom{5}{2}+\tbinom{4}{2}(n-2)+\tbinom{3}{2}=6n+1$, which is impossible, hence we need exactly $n-1$ students who solved exactly $4$ problems and a single student who solved exactly $5$ problems. This means that the only possibility is for the quantity to equal $6n+4$. As such, it also follows that there is exactly one special pair of problems $P$ such that $\tfrac{2n+1}{5}+1=2a+2$ students solved it, and every other pair of problems is solved by exactly $2a+1$ students. WLOG, number the problems $1,\ldots,6$, and assume that the student who solved $5$ problems solved $\{1,2,3,4,5\}$. The idea is to count the number of students who solved exactly four problems, with a fixed arbitrary problem $i \in \{1,2,3,4,5\}$ being one of them. Since our special pair $P$ contains at least one member of $\{1,2,3,4,5\}$, WLOG assume that $1 \in P$. Further assume that either $2 \in P$ or $6 \in P$ (that is, either $P=\{1,2\}$ or $P=\{1,6\}$), which by symmetry covers every possible case. Let $i=1$, we consider the pairs $\{1,2\},\ldots,\{1,6\}$. There are $4(2a+1)+(2a+2)=10a+6$ student-problem pair assignments in this case, counting over pairs. Since the student who solved $\{1,2,3,4,5\}$ accounts for $4$ of these, there are $10a+2$ assignments for students who solved $4$ problems. Since every such student contributes to exactly $3$ assignments, it follows that there are exactly $\tfrac{10a+2}{3}$ students who solved exactly $4$ problems, problem $1$ being one of them. In particular, this expression must be an integer. However, repeating the same process with $i=3$, we find that there are also exactly $\tfrac{10a+1}{3}$ students who solved exactly $4$ problems, problem $3$ being one of them, so $\tfrac{10a+1}{3}$ must be an integer. But this implies $\tfrac{1}{3}$ is an integer as well, which is absurd. It follows that our initial supposition cannot possibly hold, so we are done. $\blacksquare$

Suppose that there are $n$ contestants, and let contestant $i$ solve $a_i$ problems. Double counting pairs $(c, \{i, j\})$ where $\{i, j\}$ is a pair of problems solved by contestant $c$, we have the inequality $$\sum_{i=1}^n {a_i \choose 2} \geq \left \lceil \frac 25 n \right \rceil {6 \choose 2}.$$If $n \not \equiv 2 \pmod 5$, the RHS is of the form $6n + c$ for some $c \geq 5$, which implies that there must exist at least two $a_i \geq 5$ on the left. If $n \equiv 2 \pmod 5$, then we must have $6n+3$ or $6n+4$ pairs of solves. Notice that if we have $6n+3$, as ${4 \choose 2} - {2 \choose 2} = 5$ and ${4 \choose 2} - {3 \choose 2} = 3$, some combination of $3$ and $5$ must add up to $1$, which is obviously absurd. Proving that $6n+4$ solves fails is by far the most difficult part of the problem. Set $n = 5a+2$, and notice that each pair of the problems must be solved by $2a+1$ contestants, apart from one pair which is solved by $2a+2$. Double count pairs $(C, \{k, i\})$ where $C$ is a contestant and $k$ is the index of the problem which was not solved by the person who solved five problems. Fixing $\{k, i\}$, there are either $2a+1$ or $2a+2$ pairs, and fixing $C$, the number of pairs is $3$ times the number of contestants who solved $C$, which is in particular a multiple of $3$. Similarly, double counting pairs $(C, \{k, i\})$ as above but where $k$ is an index that was solved by the person who solved five problems and also not one of the two problems in the larger pair, we may fix $\{k, i\}$ again to get $2a+1$ pairs, but upon fixing $C$, there are $3$ times the number of contestants who solved $C$ plus one pairs because of the extra person. This implies that $3 \mid a$, which contradicts our earlier condition. $\blacksquare$

We will double count the number of solve pairs in total, by contestant and by pair of problems. Let the number of contestants be $n$. Claim. There exists at least one contestant that solved exactly $5$ problems. Proof. Assume otherwise. Then the number of solve pairs in total is at most $\binom42 \cdot n=6n$. But the number of solve pairs in total is strictly greater than $15\cdot\left(\frac25 n\right)=6n$, contradiction. $\blacksquare$ Now assume FTSOC that there is exactly one contestant that solved exactly $5$ problems. Call that contestant the orz contestant. Claim. $n\equiv 2\pmod 5$. Proof. Simply note how the number of solve pairs in total is at most $6n+4$, but is at least $15\left(\left\lfloor\frac25 n\right\rfloor+1\right)$. Caseworking on $n$ mod $5$ suffices. $\blacksquare$ Now let $n=5k+2$. Then each pair of problems has been solved by at least $2k+1$ contestants. Also note that $15\left(\left\lfloor\frac25 n\right\rfloor+1\right)=6n+3$, so the number of solve pairs has to be $6n+3$ or $6n+4$, so each contestant besides the orz contestant solved $4$ problems. Now assume WLOG that the orz contestant solved problems $1,2,3,4,5$. Call $P$ the set of problem pairs that don't contain problem $1$, and $Q$ the problem pairs that do contain problem $1$. Also, let $p$ be the number of pair solves with pairs in $P$ and define $q$ similarly. Note that $|P|=2|Q|$, so $p-2q\in\{1,-2\}$. However, this difference starts at $\binom42-2\cdot 4=-2$ from the orz contestant, and either decreases by $3$ or increases by $6$ from the other contestants. Therefore, $n-1$ cannot be $1$ mod $3$, so $n$ cannot be $2$ mod $3$, so $3\nmid k$. Now consider the number of solves pairs involving problem $6$. Each of them must have $2k+1$ or $2k+2$, and their total must be $10k+5$ or $10k+6$. However, since these can only be satisfied by other contestants, they come in triples, so one of these is a multiple of $3$. Since $3\nmid k$, $3\mid 10k+5$, so $k\equiv 1\pmod 3$ so $n\equiv 1\pmod 3$ and each solve pair involving problem $6$ got $2k+1$. Therefore, some other solve pair got $2k+2$. Assume WLOG this was problems $4$ and $5$. Since $3\mid n-1$, $p-2q$ must be $-2$ mod $9$, so it must be $-2$. But the extra pair does not have $1$ in it, contradiction. $\blacksquare$

Omg jatloe. Anyways, Let $n$ be the number of contestants. Let $S(i, j)$ for $1 \le i < j \le 6$ denote the total number of contestants who solved both problems $i$ and $j$. Claim: WLOG we can assume that everyone either solved $4$ or $5$ problems. Proof. A counterexample to the claim with some contestant having solved less than $4$ problems remains a counterexample with additionally dummy solves tacked on. $\blacksquare$ Claim: At least one contestant must have solved exactly $5$ problems. Proof. Assume not. However, then \[ \sum_{1 \le i < j \le 6} \frac{S(i, j)}{n} = \frac{6}{15}. \]Since $\frac{S(i, j)}{n} > \frac25$ for all $i$ and $j$, this is a contradiction. $\blacksquare$ Now suppose that only one contestant solved $5$ problems. Claim: If $n \not\equiv 2 \pmod{5}$ contradiction immediately follows. Proof. As such, it follows that \[ \sum_{1 \le i < j \le 6} \frac{S(i, j)}{n} = \frac{6}{15} + \frac{4}{n}. \]Then, it follows from $S(i, j) \ge \left\lceil \frac25 n \right\rceil$ that this can only hold if $n \equiv 2 \pmod{5}$, or else contradiction follows since the LHS is too large. $\blacksquare$ The case of $n = 5k + 2$ can thus only hold if some special $S(a, b) = 2k + 2$ while the rest are $2k + 1$. WLOG let the one contestant have solved problems $1$ through $5$. It then follows that \[ S(1, 6) + S(2, 6) + S(3, 6) + S(4, 6) + S(5, 6) \]which is either $10k + 5$ or $10k + 6$ is $3$ times the number of contestants who solved $6$. However, it follows similarily for $1 \le i \le 5$ that \[ \sum_{1 \le j \le 6, j \ne i} S(i, j) - 1 \]which is either $10k + 4$ or $10k + 5$ is $3$ times the number of contestants who solved $1$. This implies that the expression is $10k + 5$ independent of $i$, however only $S(a, b) = 2k + 2$, which can't occur in all of the expressions, contradiction.

Claim: At least 1 contestant solved 5 problems. Proof: Suppose otherwise, let us double count the number of triplets of the form $(a_i, a_j, s_k)$, where student $s_k$ solved distinct problems $a_i, a_j$ Additionally, we may assume that all students solved at least 4 problems: if not, simply consider the case where a student who solved less than 4 problems solves an additional one: the conditions would still hold. Note that we require strictly more than $15 \cdot \frac{2n}{5}=6n$ such triplets, but we have at most $\binom{4}{2} \cdot n=6n$ such triplets since each student contributes at most 6. This is a contradiction. Next, we show that contradiction also occurs if exactly one student solved 5 problems. In this case, we have at most $6n-\binom{4}{2}+\binom{5}{2}=6n+4$ such triplets. Now, note that each pair of problems must admit at least $\frac{2n+1}{5}$ triplets; hence $6n+3$ triplets are required. Additionally, note if our bound is $\frac{2n+2}{5}$ or higher, contradiction occurs. In particular, we must have that $n \equiv 2 \pmod 5$ Then, let $n=5x+2$ We now have a maximum possible of $30x+16$ triplets, with each pair of problems corresponding to at least $2x+1$ Let $p_i$ equal the number of such triplets containing the problem $i$, and $q_{a,b}$ be the number of such triplets containing problems $a,b$ Then, we have $p_i \geq 4 \cdot (2x+1) = 8x+4$ for $i=1,2 \dots 6$ Additionally, WLOG let the contestant who solved 5 problems solve $1,2,3,4,5$ Then note that $p_1 = 4 + 3 k_1$, where $k_1$ is the number of contestants who solved exactly 4 problems, including 1. In particular, if $x$ is not a multiple of 3, we need $k_1 > \frac{8x}{3}$. This is also true for $k_2, \dots k_5$, hence the minimum possible total number of triplets required is $(2x+1) \cdot 15 + \frac{1}{3} \cdot 5 > 30k+16$, which is a contradiction. (informally put, a wastage of $\frac{5}{3}$) Hence, we must have $3 | x$. Now note that $p_6 = 3k_6 \geq 8x+4$ Hence, $k_6 \geq \frac{8x}{3} +2$ (informally put, a wastage of 2) This implies that we need at least $(2x+1) \cdot 15 + 2 > 30k+16$ triplets, contradiction again. Hence we need at least 2 contestants with 5 solves, and we are done.

Kinda long solution had to take some hints to deal with the $n\equiv 2 \pmod{5}$ case. We simply double count the number of pairs $(P_1,P_2,c)$ where $P_1,P_2$ is a pair of problems solved by contestant $c$. Then, if there are $f$ students who solved 5 problems, note that, \[\binom{5}{2}f + \binom{4}{2}(n-f) \geq |(P_1,P_2,c)| \geq \binom{6}{2}\lceil{\frac{2n}{5}}\rceil\]One can do case work $\pmod{5}$ to check that this requires $f\geq 2 $ for all $n\neq 2 \pmod{5}$ and $f\geq 1$ for $n\equiv 2 \pmod{5}$. This is the case we have to check now. By way of contradiction, assume there exists only one student who solved 5 problems. WLOG, we assume that the student who solved five problems solved problems $1,2,3,4,5$. All other students have solved at most 4 problems each. Returning to the above double count by letting $n=5k+2$ we note that, \[30k+16 \geq |(P_1,P_2,c)| \geq 30k+15\]if there exists atleast one student who solved only 3 problems, then the LHS becomes at most \[\binom{5}{2}+\binom{4}{2}(5k)+\binom{3}{2}= 30k + 13 < 30k+15\]Thus, all other students except the one who solved 5 problems must have solved 4 problems each. This gives us that \[|(P_1,P_2,c)| = 10 + 6(2k+1)=30k+16\]Now, looking at the other side of the bound, we see that each pair of problems must have at most $2k+2$ solves each. Further, we cannot have 2 or more pairs of problems which had $2k+2$ solves, the left hand side becomes atleast \[13(2k+1) +2(2k+2)= 30k +17 > 30k+16\]Thus, there exists at most one pair of problems which had $2k+2$ solves. Since we already know that $|(P_1,P_2,c)|=30k+16$ this implies that we must have exactly one pair of problems which had $2k+2$ solves. Now, consider this pair of problems which had $2k+2$ solves. Then, WLOG, the only possibilities are that $(P_1,P_2)=(1,2)$ or $(P_1,P_2)=(1,6)$ (other cases are symmetric as the student who solved 5 problems solved $1,2,3,4,5$). We check each of these separately. Assume that the pair $(1,6)$ had $2k+2$ solves. We count the number of students who solved atleast one of the pairs $(1,2),(1,3),(1,4),(1,5)$ and $(1,6)$. On one hand, with multiplicities we know that this value is, \[S=4(2k+1)+(2k+2)= 10k+6\]Clearly the student who solved 5 problems solved all of these pairs and thus, contributes 4 (he has not solved the pair $(1,6)$) to this sum. Every student who solved 4 problems, contributes exactly 3 (if they have solved problem 1 and 3 other problems) or 0 (if they have not solved problem 1) to this sum. The number of students who solved atleast one of these pairs and did not solve 5 problems is \[\frac{10k+6-4}{3} = \frac{10k+2}{3} \in \mathbb{Z}\]Now, we count the number of students who solved atleast one of the pairs $(3,1),(3,2),(3,4),(3,5)$ and $(3,6)$. As before, counting with multiplicities this number is \[S= 5(2k+1)=10k+5\]The student who solved 5 problems, contributes exactly 4 to this sum (he has not solved the pair $(3,6)$) and every other student contributes either 3 (if they have solved problem 3) or 0 (if they have not solved problem 3). Thus, the number of students who solved a total of 4 problems, and at least one of the pairs in this set is, \[\frac{10k+5-4}{3} = \frac{10k+1}{3} \in \mathbb{Z}\]which is a clear contradiction. Now, assume that the pair $(1,2)$ had exactly $2k+2$ solves. Then as before, we count the number of students who solved at least one of the pairs $(1,2),(1,3),(1,4),(1,5)$ and $(1,6)$. With multiplicities this is \[4(2k+1)+2k+2 = 10k+6\]as before we obtain that, \[\frac{10k+2}{3} \in \mathbb{Z}\]Then we count the number of students who solved atleast one of the pairs $(3,1),(3,2),(3,4),(3,5)$ and $(3,6)$. As before, we obtain that, \[\frac{10k+1}{3} \in \mathbb{Z}\]which is also a contradiction. Thus, both these possibilities are impossible which implies that there exists atleast 2 students who solved atleast 5 problems as desired.

Let there be $n$ contestants. Double count the number of pairs $(P,C)$ where $P$ is a pair of problems and $C$ is a contestant who solved both. For each pair $P$, the number of contestants $C$ that solved it is at least $\left\lfloor \tfrac{2n}{5}\right\rfloor+1$, so the number of pairs is at least $15\left(\left\lfloor \tfrac{2n}{5}\right\rfloor+1\right)$. Now, suppose there are $k$ contestants that solved $5$ problems, then there are $n-k$ contestants that solved $4$ or less. Therefore, the total number of pairs $(P,C)$ is at most $6(n-k)+10k=6n+4k$. We have \[6n+4k\ge 15\left(\left\lfloor \tfrac{2n}{5}\right\rfloor+1\right)\]Let $n=5m+l$ where $0\le l\le 4$ then $30m+6l+4k\ge 30m+15+15\left\lfloor \tfrac{2l}{5}\right\rfloor$. If $l=0$ or $1$ we have $4k\ge 9$ so $k\ge 3$ and if $l=2$ or $3$ we have $4k\ge 6$ so $k\ge 2$. This leaves the case $l=2$, in which we have $k\ge 1$. Now assume for the sake of contradiction that only one person solved $5$ problems in the case $n=5m+2$. Note that every pair of problems was solved at least $2m+1$ times. All others solved at most $4$. Suppose the one person solved all problems except problem $6$. Let there be $p$ people who solved problem $6$. Then we count the number of people $C$ who solved both problem $6$ and another problem $P$. Clearly this person must come from the $p$ people, and this person solved at most $3$ other problems $P$, so the number of pairs is at most $3p$ and problem $P$ was solved by at least $2m+1$ other people so this number is at least $10m+5$. We have $3p\ge 10m+5$. Then, consider all people except the person who solved $5$ who did not solved problem $6$. There are $5m+1-p$ such people. We use the same counting strategy as we began with, discounting problem $6$. Double count the number of pairs $(P,C)$ where $P$ is a pair of problems, neither of which are problem $6$ and $C$ is a contestant who solved both, excluding the person who solved $5$ problems. Note that $p$ people solved at most $3$ problems and $5m+1-p$ people solved at most $4$ so the number of pairs is at most $3p+6(5m+1-p)=30m+6-3p$. On the other hand, for each pair of problems $P$, at least $2m$ people solved it. Thus, the number of pairs is at least $20m$ and this implies $3p\le 10m+6$, so it is equal to $10m+5$ or $10m+6$, ruling out the possibility that $m\equiv 2\pmod 3$. Now let $m=3j+i$ for $i=0,1$ then there were at most $5+(5m+1)(4)=60j+20i+9$ solves, and so a problem has at most $10j+3i+1$ solves. Let this problem be problem $1$. Now, double count the number of people $C$ who solved this problem and some other problem $P$. Now each problem $P$ must be solved at least $2m+1=6j+2i+1$ times in conjunction with problem $1$ so the number of pairs is at least $30j+10i+5$. However, of the $10j+3i+1$ people, at most one person solved $4$ other problems and the other solved at most $3$, so the number of pairs is at most $3(10j+3i+1)+1=30j+9i+4$ which is clearly not enough. We are done.

First, note that if some participant solved less than $4$ problems, let's assume he also solved some other problems so that he solved exactly $4$ problems. Doing that doesn't affecy condition from the problem statement. Now every participant solved either $4$ or $5$ problems. Suppose everyone solved $4$ problems. Then count all pairs of solved problems by a participant, say there are $n$ of them. It is exactly $6n$, but it also is $>\frac{2}{5}n*15=6n$, a contradiction. Now suppose everyone solved $4$ problems except for one student who solved $5$ problems. Note that every pair of problems is solved by at least $\frac{2}{5}n+\frac{1}{5}=\frac{2n+1}{5}$ participants. Then it is $6(n-1)+10=6n+4$, but it also is $\geq \frac{2n+1}{5}*3=6n+3$. So all pairs of problems were solved by $\frac{2n+1}{5}=a$ students except for one that was solved by $a+1$ students. And now just sum for every problem pairs of solved problems where this problem is in the pair. Then we get $4$ numbers $5a$ and two numbers $5a+1$. But summing over participants and looking $mod 3$, students who solved $4$ problems do not affect it and a student who solved $5$ makes $4$ ones and a zero, which obviously contradicts $4$ $5a$ and two $5a+1$. Thus, at least two participants solved $5$ problems

Solved at the hospital Claim: Num Students must have $n \equiv 2 \pmod 5$ or else proven easily Otherwise $0.4n$ will be 0.4, 0.6, or 0.8 less than an integer resulting in the bound (where p is problems solved per student) $\sum \binom{p}{2} \ge 2/5(15n) + 0.4(15) = 6n + 6$. Now, if at most 1 student solved 5, then this is at most than $6n + 4$, contradiction. If $n \equiv 2 \pmod 5$, then $\sum \binom{p}{2} \ge 2/5(15n) + 0.2(15) = 6n + 3$ and the only way this is possible (with less than 2 5-solvers) is with 1 5-solver and the rest 4 solvers giving $\sum \binom{p}{2} = 6n + 4$. The only way for this is if every pair of problems is solved by $0.4n + 0.2$ people except 1 pair solved by $0.4n + 1.2$ people (WLOG say this pair of problems is 1 & 4). Consider cases on the missing problem from the 5-solver: If it's p1 or p4, WLOG say it's p4. Note that p4 is part of $0 \pmod 3$ pairs of problems solved as compared to p1 being part of $1 \pmod 3$ pairs of problems (as for each 4 solver, every problem is paired up with 3 others). However, there must be an equal number of pairs of problems containing 1 and 4 ($(0.4n + 0.2) \times 4 + (0.4n + 1.2)$), contradiction. If it's not p1 or p4, WLOG say it's p6. Note that p6 is part of $0 \pmod 3$ pairs of problems solved as compared to p2 being part of $1 \pmod 3$ pairs of problems (as for each 4 solver, every problem is paired up with 3 others and for the 5 solver, every problem is paired with 4 others). However, there must be an equal number of pairs of problems containing 2 and 6 ($(0.4n + 0.2) \times 5$), contradiction.

Beautiful problem! First note that if no one has $5$ solves, then a random pair of problems is solved by at most $\frac{\binom42}{\binom62}=\frac25$ of the people, which is impossible. Thus at least one person has $5$ solves. Suppose exactly one person has $5$ solves. WLOG everyone else has $4$ solves. If there are $k$ people, each pair of problems is solved at least $\left\lfloor\frac{2k}5+1\right\rfloor$ people, and there are $6k+4$ problems solved in total. Thus $\left\lfloor\frac{2k+5}5\right\rfloor\le\frac{6k+4}{15}$ which implies $\left\lfloor\frac{2k+5}5\right\rfloor=\frac{2k+1}5$ so $k\equiv 2\pmod 5$. Letting $k=5n+2$ we get that $14$ pairs of problems are solved by $2n+1$ people, and one pair is solved by $2n+2$ people. Equivalently, $14$ pairs are missed by $3n+1$ people and one pair is missed by $3n$ people. WLOG the person with $5$ solves missed problem $1$. Let $a_{i,j}$ for $i\ne j$ be the number of people who missed exactly problems $i,j$. Notice that the number of people who missed pair $i,j$ of problems is given by $\sum_{k\ne i} a_{i,k}+\sum_{k\ne j} a_{j,k}-a_{i,j}$ and plus one if $i,j=1$. The main idea is that the sum of squares of the number of people who missed each pair is too large. The first step is to observe that \begin{align*}&\sum_{i\ne 1}\left(\sum_{k\ne 1}a_{1,k}+\sum_{k\ne i}a_{i,k}-a_{1,i}+1\right)^2+\sum_{i,j}\left(\sum_{k\ne i} a_{i,k}+\sum_{k\ne j} a_{j,k}-a_{i,j}\right)^2\\=&\sum_{i,j}a_{i,j}^2+4\left(\sum_{i,j}a_{i,j}\right)^2+2\sum_i\left(\sum_{j\ne i}a_{i,j}\right)^2+6\sum_{i\ne 1}a_{1,i}+4\sum_{i,j}a_{i,j}+5\end{align*}by comparing coefficients. Next, we have $\sum_{i,j}a_{i,j}=5n+1$. Now write $\sum_{i\ne 1}a_{1,i}=m$. Now we may write \begin{align*}&\sum_{i,j}a_{i,j}^2\\=&\sum_{i\ne 1}a_{1,i}^2+\sum_{i,j\ne 1}a_{i,j}^2\\\ge&\frac15\left(\sum_{i\ne 1}a_{1,i}\right)^2+A(m)+\frac1{10}\left(\sum_{i,j\ne 1}a_{i,j}\right)^2+B(5n+1-m)\\=&\frac15m^2+\frac1{10}(5n+1-m)^2+A(m)+B(5n+1-m)\end{align*}where $A(k)=\begin{cases}0&5\mid k\\\frac45&5\nmid k\end{cases}$ and $B(k)=\begin{cases}0&10\mid k\\\frac9{10}&10\nmid k\end{cases}$. To show this, one part is QM-AM. To show the other part, notice that for $n$ nonnegative integers $a_1,a_2,\dots,a_n$ we have $n\sum a_i^2-\left(\sum a_i\right)^2=\sum_{i\ne j}(a_i-a_j)^2$. First use smoothing to show that it suffices to consider when $a_i$ take on only two consecutive values. If the values have multiplicity $k,n-k$ then $\sum_{i\ne j}(a_i-a_j)^2\ge k(n-k)\ge n-1$, which proves the second part. Next we have \begin{align*}&\sum_i\left(\sum_{j\ne i}a_{i,j}\right)^2\\=&\left(\sum_{i\ne 1}a_{1,i}\right)^2+\sum_{i\ne 1}\left(\sum_{j\ne i}a_{i,j}\right)^2\\\ge&\left(\sum_{i\ne 1}a_{1,i}\right)^2+\frac15\left(\sum_{i\ne 1}\sum_{j\ne i}a_{i,j}\right)^2\\=&\left(\sum_{i\ne 1}a_{1,i}\right)^2+\frac15\left(\sum_{i\ne 1}a_{1,i}+2\sum_{i,j\ne 1}a_{i,j}\right)^2\\=&m^2+\frac15(10n+2-m)^2,\end{align*}by QM-AM. Thus we have \begin{align*}&\sum_{i,j}a_{i,j}^2+4\left(\sum_{i,j}a_{i,j}\right)^2+2\sum_i\left(\sum_{j\ne i}a_{i,j}\right)^2+6\sum_{i\ne 1}a_{1,i}+4\sum_{i,j}a_{i,j}+5\\\ge&\frac15m^2+\frac1{10}(5n+1-m)^2+A(m)+B(5n+1-m)\\+&4(5n+1)^2+2m^2+\frac25(10n+2-m)^2+6m+4(5n+1)+5\\=&\frac{27}{10}\left(m-\frac{15n-7}9\right)^2+135n^2+84n+\frac{196}{15}+A(m)+B(5n+1-m).\end{align*} We want to show that this is $>14(3n+1)^2+(3n)^2=135n^2+84n+14$, which is equivalent to \[\frac{27}{10}\left(m-\frac{15n-7}9\right)^2+A(m)+B(5n+1-m)>\frac{14}{15}.\] First, if $m\equiv 2,3,4\pmod 5$, or $m\equiv 1\pmod 5,5n-m\equiv 4\pmod{10}$ then $A(m)+B(5n+1-m)\ge\frac45+\frac9{10}>\frac{14}{15}$. Next, if $m\equiv 0\pmod 5$ then $A(m)+B(5n+1-m)\ge\frac9{10}$ and $9m-15n+7\equiv 2\pmod 5$ is an integer with absolute value at least $2$, so $\frac{27}{10}\left(m-\frac{15n-7}9\right)^2\ge\frac2{15}$, so $\frac2{15}+\frac9{10}>\frac{14}{15}$. Finally if $m\equiv 1\pmod 5,5n-m\equiv 9\pmod{10}$ we have $9m-15n+7\equiv 16\pmod{30}$, so it is an integer with absolute value at least $14$, so $\frac{27}{10}\left(m-\frac{15n-7}9\right)^2\ge\frac{98}{15}>\frac{14}{15}$. This is all cases, so it is impossible for exactly one person to have $5$ solves. Thus at least two people have $5$ solves, as desired.