Maths Olympiad Prep

Library / /231 of 299

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it Iran

There are 2n2n beakers and k<nk < n chemical substances. In these beakers, we, in aggregate, have 2k2k grams of each substance and the weight of every substance in each beaker is a non-negative real number. Find the smallest value of ss such that we can find ss beaker(s) that in aggregate contains at least 22 grams of each substance.

Solution

We claim that the answer is n+1n+1.

For sake of proving that we at least need n+1n+1 beakers, consider the case that n1n-1 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 n1n-1 beakers and we would need two beakers, for sake of completing the last substance, since 2k2kn+1<2\frac{2k}{2k-n+1} < 2.

Assume now the weight of each substance in each beaker is less than 22 grams. We shall then prove the following lemma:

Lemma 1. If we write the beakers according to the weight of the jj-th substance in descending order, i.e., a1,,a2ka_1, \dots, a_{2k}; then as+a2ks2a_s + a_{2k-s} \ge 2 for some sks \le k.
Proof. Since (a1+a2k)+(a2+a2k1)++(ak+ak+1)=2k(a_1 + a_{2k}) + (a_2 + a_{2k-1}) + \dots + (a_k + a_{k+1}) = 2k 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 iji_j. Assume that we labeled the substances in a way that the sequence (ij)(i_j) is non-decreasing. We denote by excellent and good all the beakers that the weight of the jj-th substance in them is greater than or equal to aija_{i_j} and a2nija_{2n-i_j}, respectively. Then we need the following lemma.

Lemma 2. For each two colors A,BA, B we at least have two beakers that are simultaneously AA-good and BB-good.
Proof. Since ij<k+1i_j < k+1 it follows that we at least have k+1k+1 good beakers of both colors. Since we in total have 2k2k beakers, we are done.

Now, if there is a beaker such that is simultaneously AA-excellent and BB-excellent, then there would also be an additional beaker which is simultaneously AA-good and BB-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 jj-good and j+1j+1-excellent.
Proof. According to our ordering, we have ij+1iji_{j+1} \ge i_j. We shall thus at least have iji_j beakers which are j+1j+1-excellent. While, we only have ij1i_j - 1 beakers which are not jj-good. This completes our proof.

Now, choose the first beaker such that is 11-excellent, choose the second one such that is 11-good and 22-excellent, ..., continuing this way, we shall choose the last beaker such that it is nn-good. We are done. \blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.