A family wears clothes of three colors: red,blue and green,with a separate,identical laundry bin for each color. At the beginning of the first week,all bins are empty.Each week,the family generates a total of $10 kg $ of laundry(the proportion of each color is subject to variation).The laundry is sorted by color and placed in the bins.Next,the heaviest bin(only one of them,if there are several that are heaviest)is emptied and its content swashed.What is the minimal possible storing capacity required of the laundry bins in order for them never to overflow?
Problem
Source: Baltic Way 2015
Tags: combinatorics
30.11.2015 23:48
This is somewhat similar to C5 of IMO Shortlist 2009. I claim that the minimal possible storing capacity is $25kg$. Let us first give an example to prove that $25kg$ is required. The family equally generates $(3 + \frac{1}{3}) kg$ of each colour the first day. Then every next week, once a bin is emptied, the family refills the bin to have equal mass to the other two bins, and then equally distributes the remaining laundry among the three bins. It is easy to see that we can reach a number as close to $10kg$ as we want in two bins after emptying the third by just repeating this process. To prove this consider the limit of the sequence $f(n + 1) = \frac{2}{3}f(n) + \frac{10}{3}$, where $f(1) = \frac{10}{3}$. Then once close enough, the family puts $5kg$ in each of the two bins that weren't emptied, reaching any mass less than $15kg$ in both. Then finally, the family puts $10kg$ in the only non-empty bin, reaching every mass less than $25kg$. Now we need to prove that $25kg$ is enough. I will prove that after every week (after cleaning the laundry). Note that in the beginning, all the bins are empty. Now suppose that there are two bins with masses $a$ and $b$ such that $a < 15kg$, $b < 15kg$ and $a + b < 20kg$. Let the family add the laundry in such a way that we have bins containing masses $a + x$, $b + y$ and $z$, such that $x + y + z = 10kg$. $1)$ If $z > a + x$ and $z > b + y$, then $(a + x) + (b + y) < 2\cdot z < 20kg$ and $15kg >10kg > z > a+x$, and also $15kg > z > b + y$. $2)$ If $a + x > z$ and $a + x > b + y$, then $\frac{3}{2}(b + y + z) < a + x + b + y + z < 20kg + 10kg = 30kg$, so the remaining mass $b + y + z < 20kg$, also it's trivial that $z < 10kg $ and if $b + y \ge 15kg$, we have that $a + x + b + y \ge 2*(b + y) \ge 30kg$, but this is impossible because $a + x + b + y < 20kg + x + y + z = 30kg$ That means that at the beginning of each week, no bin has more than $15kg$ of laundry, so $25kg$ is enough. We proceed in a similar way if $b + y$ has the most mass.
14.08.2021 00:26
IMO SL 2009 C5 vibes. Answer. $\boxed{25}$. For the construction, firstly add $\frac{10-x}{3}$ to both bin $1$ and $2$ and we add $\frac{2x+10}{3}$ to bin $3$, where $x$ is the amount in bin $1$ before, this makes all bins having same value, hence it does not matter which bin gets emptied, wlog always bin $3$ in order to make this procedure work. Notice that we can do this as long as $x\leq 10$. Hence, we get after infinite number of such procedures, before operation, every bin contains $10$. Hence after operation we have two bins with $10$ and third is on $0$. Now add $5$ to both bins with $10$. Thus both bins before the operation contain $15$. After operation we have one $15$ bin and two bins that are empty. Hence, we get that storing capacity here must be $25$. Call the emptying heaviest bin as an operation. [asy][asy] size(4cm);defaultpen(fontsize(10pt));pen org=magenta;pen med=mediummagenta;pen light=pink;pen deep=deepmagenta;pen dark=darkmagenta;pen heavy=heavymagenta; draw((-1,3)--(-1,0)--(1,0)--(1,3)); draw((-4,3)--(-4,0)--(-2,0)--(-2,3)); draw((2,3)--(2,0)--(4,0)--(4,3)); label("$1$",(-3,0),S);label("$2$",(0,0),S); label("$3$",(3,0),S); label("$x+z_1$",(-3,1.5));label("$0+z_2$",(0,1.5)); label("$y+z_3$",(3,1.5)); [/asy][/asy] Claim. After every operation, sum of all bins is less than or equal to $20$. Proof. After an operation, let bin $1$ contain $x$, let bin $2$ contain $0$ and let bin $3$ contain $y$. As after very first operation the statement is true, we assume that $x+y\leq 20$. Now let us add $z_1,z_2,z_3$ to bin $1,2,3$, respectively. Note that $z_1+z_2+z_3=10$. Now we split this into cases: Suppose bin $1$ is the heaviest. Hence, $x+z_1\geq z_2,x+z_1\geq y+z_3$. We have, $$20+2z_1\geq 20+z_1-z_3\geq x+y+z_1-z_3\geq 2y \implies y\leq 10+z_1.$$Thus, $y+z_2+z_3=10+y-z_1\leq 20$. Suppose bin $2$ is the heaviest. Hence, $z_2\geq x+z_1,z_2\geq y+z_3$. We have, $$x+z_1+y+z_3\leq 2z_1\leq 2(10-z_2-z_3)\leq 20.$$ Suppose bin $3$ is the heaviest. This case is exactly the same as the first case. By the claim, we have right before every operation sum of all bins less than or equal to $x+y+10\leq 30$. Thus, before every operation the second largest bin is less than or equal to $15$, as otherwise sum of all bins is greater than $30$. As the second largest bin does empty during the operation, we get desired bound.