3
$\begingroup$

I found a maths puzzle somewhere and a part of it as below:

Kelly wants to place n objects $a_1,a_2,⋅⋅⋅,a_n$ into two bags. For each $i=1,2,⋅⋅⋅,n$, the weight of $a_i$ is $w_i$ kilograms.

The capacity of each bag is not a problem as it is not limited.

Kelly wants to minimize the weight of the most heavy bag. So this is what she does:

She ordered in an arbitrary order. She always places the object under consideration into the least heavy bag.

At the end when all objects are in the bags, Kelly finds that the weight of the most heavy bag is at most 3/2 times the optimum.

How? ? ? How can she get to know that?

Extended version of Weights - Objects into bags puzzle.

Any examples would make me understand better.Can we deduce a formula for such cases?

$\endgroup$
1
  • $\begingroup$ Where is this question from? $\endgroup$
    – dtldarek
    Commented Dec 12, 2014 at 19:58

2 Answers 2

2
$\begingroup$

let the sum of weights be $2s+m$ and let $m$ be the weight of the heaviest bag, then the heaviest the heavier side can get with the proposed method is $s+m$.

On the other hand the heavier side will always weight at least $\frac{2s+m}{2}$.

So we get the ratio of the heavy bag over the optimum is at most $\dfrac{s+m}{\frac{2s+m}{2}}=\dfrac{2s+2m}{2s+m}=1+\frac{m}{2s+m}$.

if $m$ is less than half of the total weight we are done, if $m$ is more than half of the total weight the optimum is clearly when $m$ is alone in the bag. And the worst case scenario is when the heavier bag has $m+s$ and the other side $s$. In this case the ratio of the worst case vs the optimum is $\frac{s+m}{m}=1+\frac{s}{m}$ which is less than $1+\frac{1}{2}$ since $m$ is at least twice as $s$ in this case.

$\endgroup$
6
  • $\begingroup$ what is $s$ here? $\endgroup$ Commented Dec 13, 2014 at 0:23
  • $\begingroup$ We denotes by $2s+m$ the total weight of the objects and by $m$ the heaviest object, so I guess $s$ is half of the weight of all objects except the heaviest. $\endgroup$
    – Asinomás
    Commented Dec 13, 2014 at 0:26
  • $\begingroup$ Also, I didn't understand, what do you meant by "In this case the ratio of the worst case vs the actual" ...what is actual? $\endgroup$ Commented Dec 13, 2014 at 0:38
  • $\begingroup$ sorry it should say optimal. $\endgroup$
    – Asinomás
    Commented Dec 13, 2014 at 0:44
  • 1
    $\begingroup$ Thanks a lot Jorge. Now I understood. $\endgroup$ Commented Dec 13, 2014 at 1:34
1
$\begingroup$

Hints:

  • Use exactly the same reasoning as in my answer to your previous question, just devise a stronger inequality.
  • When adding an item of weight $w$, the weight of the bag with the smallest load is at most $$\frac{2M-w}{2}.$$

I hope that helps $\ddot\smile$

$\endgroup$

You must log in to answer this question.

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