Skip to main content
2 of 4
added 6 characters in body
Morteza
  • 628
  • 3
  • 10

N students - n exams

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(nlogn)$ upper bound for $N$.)

Morteza
  • 628
  • 3
  • 10