An interesting problem

Revision en2, by farmersrice, 2019-06-03 06:35:53

You have $N$ cups, each containing some amount of water. Each cup is identical and has maximum capacity $M$ milliliters. In one operation, you may select any two cups $a$ and $b$, which represents pouring water from cup $a$ to cup $b$. If the sum of the cups' volume is less than or equal to $M$, cup $a$ ends up empty and cup $b$ contains all the volume of the cups. If the sum of the cups' volume is greater than $M$, then cup $b$ ends up filled to capacity $M$ and cup $a$ contains the remainder of the water. Suppose the total volume of water in all cups is $V$. The question is: What is the minimum number of operations necessary to create $\left \lfloor{\frac{V}{M}}\right \rfloor$ cups of water that are filled to maximum capacity?

No constraints, the problem is original and comes from a real life scenario. My hypothesis is that as long as you merge small to large then it will take the same number of operations, which is also optimal — but I can't think of how to prove this. Any ideas?

#### History

Revisions Rev. Lang. By When Δ Comment
en2 farmersrice 2019-06-03 06:35:53 227
en1 farmersrice 2019-06-03 06:34:06 835 Initial revision (published)