Maths Olympiad Prep

Library / /3 of 13

, 2015

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Baltic Way

A family wears three colours of clothing: red, blue and green, with a separate laundry bin for each colour. Each week, the family generates a total of KK kilogrammes of laundry (the proportion of each colour is subject to variation). The laundry is first sorted by colour and disposed of in the bins. Next, the heaviest bin is emptied and its contents washed. What is the storing capacity required of the laundry bins if they must never overflow?

Solution

Answer: 52K\frac{5}{2}K.
Each week, the accumulation of laundry increases the total amount by KK, after which the washing decreases it by at least one third, because, by the pigeon-hole principle, the bin with the most laundry must contain at least a third of the total. Hence the amount of laundry post-wash after the nnth week is bounded above by the sequence an+1=23(an+K)a_{n+1} = \frac{2}{3}(a_n + K) with a0=0a_0 = 0, which is clearly bounded above by 2K2K. The total amount of laundry is less than 2K2K post-wash and 3K3K pre-wash.

Now suppose pre-wash state (a,b,c)(a, b, c) precedes post-wash state (a,b,0)(a, b, 0), which precedes pre-wash state (a,b,c)(a', b', c'). The relations aca \le c and aa+Ka' \le a + K lead to
3K>a+b+c2a2(aK), 3K > a + b + c \ge 2a \ge 2(a' - K),
and similarly for bb', whence a,b<52Ka', b' < \frac{5}{2}K. Since also cKc' \le K, a pre-wash bin, and a fortiori a post-wash bin, always contains less than 52K\frac{5}{2}K.

Consider now the following scenario. For a start, we keep packing the three bins equally full before washing. Initialising at (0,0,0)(0, 0, 0), the first week will end at (13K,13K,13K)(\frac{1}{3}K, \frac{1}{3}K, \frac{1}{3}K) pre-wash and (13K,13K,0)(\frac{1}{3}K, \frac{1}{3}K, 0) post-wash, the second week at (59K,59K,59K)(\frac{5}{9}K, \frac{5}{9}K, \frac{5}{9}K) pre-wash and (59K,59K,0)(\frac{5}{9}K, \frac{5}{9}K, 0) post-wash, &c. Following this scheme, we can get arbitrarily close to the state (K,K,0)(K, K, 0) after washing. Supposing this accomplished, placing 12K\frac{1}{2}K kg of laundry in each of the non-empty bins leaves us in a state close to (32K,32K,0)(\frac{3}{2}K, \frac{3}{2}K, 0) pre-wash and (32K,0,0)(\frac{3}{2}K, 0, 0) post-wash. Finally, the next week's worth of laundry is directed solely to the single non-empty bin. It may thus contain any amount of laundry below 52K\frac{5}{2}K kg. \square

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.