# Dropping the “Lowest Grade” Problem

Let $A=\{a_1, a_2, ... , a_n\}$ be a set of non-negative real numbers and $B=\{b_1, b_2, ..., b_n\}$ be sets of positive real numbers.

Let $s = \dfrac{ \sum_A a}{\sum_B b} = \dfrac{a_1+a_2+\dots+a_n}{b_1+b_2+\dots+b_n}$.

What I want to do find $k$ so that

$s_1 = \dfrac{\sum_{A-\{a_k\}} a }{\sum_{B-\{b_k\}} b}$ is the largest.

And more generally, find

$s_p = \dfrac{\sum_{A-\{a_{k_1},a_{k_2},\dots,a_{k_p}\}} a }{\sum_{B-\{b_{k_1},b_{k_2},\dots,b_{k_p}\}} b}$

I'm not exactly sure what this is called, and I tried doing a google search but I wasn't able to find what I am looking for.

And of course, I can do this by exhaustion, but I feel that there should be a smart way to figure this out...

• Unless something is known in advance about the elements of that set, there's not much that can be done. – apnorton Dec 12 '14 at 1:25
• @anorton So nothing other than brute force? – Braindead Dec 12 '14 at 1:26
• Depends on what you mean by brute force, but yes. Clearly you want to remove the smallest $p$ elements from $A$ and the largest $p$ elements from $B$. Thus, you just have to find the biggest/smallest elements of a set. If you're worried about asymptotic performance for a program, I believe there are linear-time algorithms for finding the least/greatest $p$ elements of a set. – apnorton Dec 12 '14 at 1:29
• @anorton: I think he is deleting matching elements, that the sets are really sequences. – Ross Millikan Dec 12 '14 at 1:30
• @RossMillikan,@anorton: Yup, I want to delete matching elements. – Braindead Dec 12 '14 at 1:31

The naive thing is to delete the smallest $\frac {a_i}{b_i}$, but this fails. Let $A=(1,51,100), B=(2,100,100).$ The worst grade is $\frac 12$, but deleting it leaves $\frac {151}{200}$, while deleting the $\frac {51}{100}$ leaves $\frac {101}{102}$, much better. The simple approach is to scale the tests to the same possible score, then it is easy.
• Hmm... it appears dropping the $k$ with the largest $b_k - a_k$ seems to do the trick. – Braindead Dec 12 '14 at 3:10
• I don't think that works, either. Let $A=(1,2,100), B=(2,4,103)$. At the start you have $\frac {103}{109}$, but dropping the last leaves you with $\frac 36$ – Ross Millikan Dec 12 '14 at 3:23