2
$\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 $k > 1$ 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 2 times the optimum.

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

$\endgroup$
  • $\begingroup$ Though not an answer, curious to know what will happen when we know the number of bags. Say the number of Bags will be two. Then what will be the relation between Optimal bag weight and heaviest bag among the two? $\endgroup$ – Technopolice Dec 12 '14 at 18:24
4
$\begingroup$

Denote by $M$ the optimal weight of the most heavy bag.

Hint:

  • At all times, the weigh of the least heavy bag has to be smaller than $M$ (consider the total weight of items).
  • The weigh of any item has to be smaller or equal than $M$ (the most heavy item has to go somewhere).

I hope this helps $\ddot\smile$

$\endgroup$
  • $\begingroup$ :(... That didn't help me to understand how. $\endgroup$ – kingmakerking Dec 12 '14 at 16:26
  • $\begingroup$ What do you have a problem with? $\endgroup$ – dtldarek Dec 12 '14 at 16:27
  • $\begingroup$ On your hint, how will Kelly knows "weight of the most heavy bag is at most 2 times the optimum"? $\endgroup$ – kingmakerking Dec 12 '14 at 16:32
  • $\begingroup$ @kingmakerking Because the weight of any bag will be at most $2\cdot M$. $\endgroup$ – dtldarek Dec 12 '14 at 16:33
  • $\begingroup$ How? :( ( I guess I am super dumb). What happens if it is more than 2M? Or how do you say it is 2M? $\endgroup$ – kingmakerking Dec 12 '14 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.