Skip to main content
MathOverflow

Return to Answer

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

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.

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.

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.

Source Link
Will Brian
Will Brian
  • 18.6k
  • 3
  • 79
  • 106

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.