n bag of sand and one algorithms

Question

We have $n$ bags of sand, with volume $$v_1,...,v_n, \forall i: \space 0 < v_i < 1$$ but not essentially sorted. we want to place all bag to boxes with volumes 1. We propose one algorithm:

At first we place all bags in the original order. Then we select one box and place on it, bag $1, 2, 3,...$ until these can be place in box. If the $i^{th}$ bag couldn't be inserted in a box, we choose another box and place it $i^{th}, i^{th+1},...$ until these can be place in the box.

If the number of boxes that be used in this algorithms $X$, and the number of boxes used in minimum way (by using minimum algorithms) be $Y$, why always $X > Y$ is false, and always true that $X < 2Y$.

Answer 1

In the best efficient way, each box is completely full:

$$Y=\Sigma v_i$$

So in general

$$Y\ge \Sigma v_i$$

In addition, in your algorithm, each two consecutive box must have at least one unit sand (otherwise the first box could accommodate the next one). So, even in the worst case:

$$\Sigma v_i>\frac X2$$

when X is even and

$$\Sigma v_i>\frac {X-1}2$$ when X is odd.

Combining two in-equations:

$$\frac X2 < \Sigma v_i \le Y$$

or

$$X < 2Y$$

for when X is even.

for odd cases of X we have $$X < 2Y+1$$

However, since 2Y is even, X=2Y does not happen and it can be re-written as:

$$X < 2Y$$

So, for both odd and even cases of X:

$$X < 2Y$$

Answer 2

If $Y$ is the minimum number of boxes used by any algorithm and $X$ is the number of boxes used by your algorithm, then it must be that $X\ge Y$ simply by the way we defined $Y$.

If $X<Y$, then $Y$ couldn't be the minimum number of boxes used by any algorithm because your algorithm produces a smaller result.

It may be that you can prove that $X<2Y$, but that doesn't contradict anything about our discussion above.