We have $N$ students and $n$ exams. We need to select $n$ out of the students using the grade of those exams. The procedure is as follows:


1- We set some ordering on the exams.


2- Going through this order, In every exam, the best student will be selected and we forget about his/her grade in the next exams.


Now we have all grades and we know that before setting the ordering on the exams, all the student are hopeful to be selected. How large can $N$ be in terms of $n$?


(As far as I remember, we proved a $2n+c$ lower bound and an $O(n\log n)$ upper bound for $N$.)



Lower bound for a combinatorial problem ($N$ students taking $n$ exams)
**My initial argument was erroneous. I'm rewriting everything completely.**


Denote by $f(n)$ the maximal value of $N$ for that value of $n$. I claim that $$
 f(k+\ell)\geq f(k)+f(\ell)+k \qquad\text{for all $k\leq \ell$.}
 \qquad\qquad(\*)
$$
In a standard way, this shows that $f(n)\geq 1+\frac12n\log\_2 n$.


To prove $(\*)$, assume that we have $k+\ell$ exams. Take a set $X$ of $f(k)$ students hopeful for the first $k$ exams and hopeless for the last $\ell$, and take a set $Y$ of $f(\ell)$ students performing in the opposite way. Finally, take a set $Z$ of $k$ students, each of which wins his own exam in the first group and his own exam in the last group and not attenfing the others. 


Now, if the first $k$ exams are taken into account first, then $Z$ win their exams and become out of competition, so $Y$ are still hopeful. Similarly, $X$ stay hopeful if the last $\ell$ exams are taken into account first.


