1
$\begingroup$

Suppose we want to produce $x,y,z$ amount of red, blue, green balls, respectively, using a machine. This machine can produce either (1) 2 balls of the same color in 1 day, or (2) one ball of each color in 1 day. What is the minimum number of days to produce the required number of balls of each color? Note that you can exceed the number of required balls of each color.

I think the greedy approach is optimal here, but I'm not sure how to prove it is optimal. By greedy, what I mean is we're going to initially use option (2) $\min(x,y,z)$ times. Let's just assume $x = \min(x, y, z)$ without loss of generality. Afterwards, we will need $y - x$ blue and $z - x$ green balls. At this point, I propose that we use option (1) $\big\lfloor \frac{y - x}{2} \big\rfloor + \big\lfloor \frac{z - x}{2} \big\rfloor$ times.

After this point, we will have either acquired all the balls needed (i.e., $y-x$ and $z-x$ are both even), or red and/or green needs one more ball (which takes 1 more day using option (2)).

So if we define $a = \max(x,y,z)$, $c = \min(x,y,z)$, $b = \{x, y, z \} \setminus \{a, c\}$, I am proposing that the optimal solution is $$ c + \bigg\lfloor \frac{a - c}{2} \bigg\rfloor + \bigg\lfloor \frac{b - c}{2} \bigg\rfloor + \bigg\lceil \frac{(a - c) \mod 2 + (b - c) \mod 2}{2} \bigg\rceil $$

or $$ c + \bigg\lceil \frac{a+b-2c}{2} \bigg\rceil $$

Is this solution optimal? If so, how do I prove its optimality?

$\endgroup$
2
  • $\begingroup$ Do you mean using option (2) $min(x, y, z)$ times and then using option (1)? I assume this is a typo. $\endgroup$ Commented Jul 11, 2021 at 23:04
  • $\begingroup$ @MarkSaving Oops, yes, I had the (1) and (2) swapped. Just now fixed it $\endgroup$
    – 24n8
    Commented Jul 11, 2021 at 23:14

1 Answer 1

1
$\begingroup$

Edit: your solution is in fact optimal. I misunderstood it originally. A simpler solution is below.

Consider the case where, WLOG, $x \leq y \leq z$. The correct solution is to get one ball of each colour $y$ times, and then get two balls of the green colour as many times as necessary (which will be $ceil(\frac{z - y}{2})$ times).

It's relatively easy to prove this solution is correct. For consider any solution in which we use option (1) on two different colours: then WLOG we could have used option (2) twice. So WLOG any other solution will consist only of using option (2) and using option (1) on exactly 1 colour. And it's clear that WLOG, we can assume that colour to be green. So clearly, this hypothetical other solution is no better than ours.

Your solution is identical to mine since it replaces $2n$ uses of option (2) with $n$ uses of option (1) on blue and $n$ uses of option (1) on green for some $n$.

$\endgroup$
3
  • $\begingroup$ I don't understand your first paragraph. For that example, my solution would use option (1) and not option (2)? I realized I had a typo in one of the sentences, but the equations that I have are correct. $\endgroup$
    – 24n8
    Commented Jul 11, 2021 at 22:46
  • $\begingroup$ For your second paragraph, is there an example where your strategy gives a smaller number of days than mine? I couldn't come up with one. It seems to give the same result as mine. $\endgroup$
    – 24n8
    Commented Jul 11, 2021 at 22:50
  • $\begingroup$ @24n8 Sorry, misunderstood your solution. Your solution is also optimal: see the edit. $\endgroup$ Commented Jul 11, 2021 at 23:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .