There are beakers and chemical substances. In these beakers, we, in aggregate, have grams of each substance and the weight of every substance in each beaker is a non-negative real number. Find the smallest value of such that we can find beaker(s) that in aggregate contains at least grams of each substance.
Solution
We claim that the answer is .
For sake of proving that we at least need beakers, consider the case that of these substances are completely in one beaker and the last substance is equally distributed into the remaining beakers. Thus, we need to choose the first beakers and we would need two beakers, for sake of completing the last substance, since .
Assume now the weight of each substance in each beaker is less than grams. We shall then prove the following lemma:
Lemma 1. If we write the beakers according to the weight of the -th substance in descending order, i.e., ; then for some .
Proof. Since then at least one of the terms above is at least two. This completes our proof.
Let us denote the smallest index with the afore-mentioned property by . Assume that we labeled the substances in a way that the sequence is non-decreasing. We denote by excellent and good all the beakers that the weight of the -th substance in them is greater than or equal to and , respectively. Then we need the following lemma.
Lemma 2. For each two colors we at least have two beakers that are simultaneously -good and -good.
Proof. Since it follows that we at least have good beakers of both colors. Since we in total have beakers, we are done.
Now, if there is a beaker such that is simultaneously -excellent and -excellent, then there would also be an additional beaker which is simultaneously -good and -good. After removing this beaker we can resolve the case for at least two colors and for the colors that are still the case in line
Finally, we need the following lemma:
Lemma 3. There is a beaker which is simultaneously -good and -excellent.
Proof. According to our ordering, we have . We shall thus at least have beakers which are -excellent. While, we only have beakers which are not -good. This completes our proof.
Now, choose the first beaker such that is -excellent, choose the second one such that is -good and -excellent, ..., continuing this way, we shall choose the last beaker such that it is -good. We are done.