Lower bound for a combinatorial problem ($N$ students taking $n$ exams)

Question

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$.)

Answer 1

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.

Answer 2

A better-than-linear lower bound for $N$ is $\frac{1}{4} (n \log_2 n + n)$.

To see why, let's look at what you can do when $n$ is a power of $2$.

For $n = 2^1 = 2$, we may take $N_2=3$. Our $N=3$ students are called $a,b,c$, and in our $n=2$ exams, the top two students are:

Exam 1: $\ a \ \ b$

Exam 2: $\ a \ \ c$

It is clear that student $a$ will be selected in the first round, and then either $b$ or $c$ will be selected next, depending on the ordering of the exams.

For $n = 2^2 = 4$, we may take $N_4=8$. Our $N=8$ students are called $a,b,c,d,e,f,g,h$, and in our $n=4$ exams, the top four students are:

Exam 1: $\ a \ \ b \ \ c \ \ e$

Exam 2: $\ a \ \ b \ \ c \ \ f$

Exam 3: $\ a \ \ b \ \ d \ \ g$

Exam 4: $\ a \ \ b \ \ d \ \ h$

It is clear that student $a$ and $b$ will be selected in the first two rounds. No one else is guaranteed selection, but it is not difficult to check that any given student is selected for some ordering of the four exams.

For $n = 2^3 = 8$, we may take $N_8=20$. Our $N=20$ students are called $a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t$, and in our $n=8$ exams, the top eight students are:

Exam 1: $\ a \ \ b \ \ c \ \ d \ \ \ e \ \ g \ \ i \ \ m$

Exam 2: $\ a \ \ b \ \ c \ \ d \ \ \ e \ \ g \ \ i \ \ n$

Exam 3: $\ a \ \ b \ \ c \ \ d \ \ \ e \ \ g \ \ j \ \ o$

Exam 4: $\ a \ \ b \ \ c \ \ d \ \ \ e \ \ g \ \ j \ \ p$

Exam 5: $\ a \ \ b \ \ c \ \ d \ \ f \ \ h \ \ k \ \ q$

Exam 6: $\ a \ \ b \ \ c \ \ d \ \ f \ \ h \ \ k \ \ r$

Exam 7: $\ a \ \ b \ \ c \ \ d \ \ f \ \ h \ \ l \ \ s$

Exam 8: $\ a \ \ b \ \ c \ \ d \ \ f \ \ h \ \ l \ \ t$

This time students $a - d$ are guaranteed selection, but no one else is. Again, it is not difficult to check that any given student is selected for some ordering of the four exams.

Without going to the trouble of writing down a formal recurrence for this pattern, you can check that if $n = 2^k$ then a solution like this leads to a situation where $$N = 2^{k-1} \cdot 1 + 2^{k-2} \cdot 2 + 2^{k-3} \cdot 4 + 2 \cdot 2^{k-2} + 1 \cdot 2^{k-1} + 2^k = 2^{k-1}(k + 2).$$ Putting everything in terms of $n$, this is $N_{2^k} = \frac{n}{2}(\log_2 n + 2)$.

For some $n$ that is not a power of $2$, we can (crudely) just round down to the nearest power of $2$ for the desired solution: pick $k$ such that $2^k < n \leq 2^{k+1}$ and then observe that $$N_n \geq N_{2^k} \geq (k+2)2^{k-1} = \frac{1}{4}(2^{k+1} \cdot k + 2 \cdot 2^{k+1}) = \frac{1}{4}(2^{k+1}(k+1) + 2^{m+1}) \geq \frac{1}{4}(n \log_2 n+n)$$ as claimed.