Skip to main content
1 of 2
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

Denote by $f(n)$ the maximal value of $N$ for that value of $n$. I claim that for any $k$, $\ell$, and $d$ such that $d\leq\min\{k,f(\ell)\}$ we have $$ f(k+\ell)\geq f(k)+d+f(\ell). \qquad\qquad(*) $$

Assume that we have $k+\ell$ exams. Take the set $X$ of $f(k)$ students hopeful for the first $k$ exams; let them get lowest marks on the other $\ell$ exams. Take the set $Y$ of $d(\leq f(\ell))$ students hopeful for the final $\ell$ exams. Let each of them get the highest mark on his own exam out of the first $k$ (this is possible due to $k\geq d$). Finally, take another set $Z$ of $f(\ell)$ students: they are weaker than $Y$ on he final $\ell$ exams, but, if $Y$ go away, they wil be hopeful for those. Next, $Z$ are hopeless for the first $k$ exams.

Now, if the final $\ell$ exams go first, and the first $k$ exams go last, all the students from $Y$ and $X$ become hopeful. For the reverse order, $Y$ beat everyone on their $f(\ell)$ exams, some of $X$ fill the gaps, and then $Z$ get their chance. So $(*)$ has been proved.


The asmptotics of the minimal sequence subject to $(*)$ and $f(1)=1$ is not that clear to me; but, according to Maple, the ratio of i and $n\log n$ increases. I'll try to proceed on this.

Ilya Bogdanov
  • 23.7k
  • 54
  • 92