Greedy laundry bins: why total load gives the wrong capacity bound

spriggan_8·Oct 4, 2025(edited)

The total before a wash stays below 3K, but the proposed answer for each bin is 5K/2. How do we improve a total-load bound into a sharp bound for one bin? Problem: 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

K

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? Source: Baltic Way 2015 Shortlisted Problems · MNET-01CP

Open MNET-01CP in the question bank →

5 replies

MissingNo404·Oct 4, 2025(edited)

The post-wash total satisfies

T_{r+1}\le(2/3)(T_r+K)

, so it stays below 2K from empty bins. Consequently the pre-wash total stays below 3K.

spriggan_8·Oct 4, 2025(edited)

That only gives each bin below 3K. What extra information does washing the heaviest bin give?

MissingNo404·Oct 4, 2025(edited)

If a bin retains a units after a wash, the washed bin had at least a. Before that wash the total was at least 2a and below 3K, so a<3K/2. Next week it receives at most K, giving less than 5K/2. A just-emptied bin receives at most K.

tarnished_ish·Oct 5, 2025(edited)

For sharpness, repeatedly equalize the three bins before washing; post-wash states approach (K,K,0). Then split the next K equally between the two nonempty bins, wash one, and put the following week's full K into the survivor. Its load approaches 5K/2.

spriggan_8·Oct 5, 2025(edited)

So the capacity is the supremum 5K/2, although finite play from empty bins never quite reaches it. That handles why a slightly smaller capacity eventually fails.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…

Greedy laundry bins: why total load gives the wrong capacity bound

spriggan_8·Oct 4, 2025(edited)

K

Open MNET-01CP in the question bank →

5 replies

MissingNo404·Oct 4, 2025(edited)

The post-wash total satisfies

T_{r+1}\le(2/3)(T_r+K)

, so it stays below 2K from empty bins. Consequently the pre-wash total stays below 3K.

spriggan_8·Oct 4, 2025(edited)

That only gives each bin below 3K. What extra information does washing the heaviest bin give?

MissingNo404·Oct 4, 2025(edited)

tarnished_ish·Oct 5, 2025(edited)

spriggan_8·Oct 5, 2025(edited)

So the capacity is the supremum 5K/2, although finite play from empty bins never quite reaches it. That handles why a slightly smaller capacity eventually fails.