Skip to main content
The initial argument was wrong; everything is rewritten.
Source Link
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

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 for any $k$, $\ell$$$ f(k+\ell)\geq f(k)+f(\ell)+k \qquad\text{for all $k\leq \ell$.} \qquad\qquad(*) $$ In a standard way, and $d$ suchthis shows that $d\leq\min\{k,f(\ell)\}$ we have $$ f(k+\ell)\geq f(k)+d+f(\ell). \qquad\qquad(*) $$$f(n)\geq 1+\frac12n\log_2 n$.

AssumeTo prove $(*)$, assume that we have $k+\ell$ exams. Take thea set $X$ of $f(k)$ students hopeful for the first $k$ exams; let them get lowest marks onexams and hopeless for the otherlast $\ell$ exams. Take the, and take a set $Y$ of $d(\leq f(\ell))$$f(\ell)$ students hopeful for the final $\ell$ exams. Let each of them get the highest mark on his own exam out ofperforming in the first $k$ (this is possible due to $k\geq d$)opposite way. Finally, take anothera set $Z$ of $f(\ell)$$k$ 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 foreach of which wins his own exam in the first $k$ examsgroup and his own exam in the last group and not attenfing the others.

Now, if the final $\ell$ exams go first, and the first $k$ exams go lastare taken into account first, all the students fromthen $Y$$Z$ win their exams and $X$ become hopeful. For the reverse orderout of competition, so $Y$ beat everyone on their $f(\ell)$ examsare still hopeful. Similarly, 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,stay hopeful if the ratio of i andlast $n\log n$ increases. I'll try to proceed on this$\ell$ exams are taken into account first.

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.

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.

Source Link
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.