A property regarding intervals

Question

While I was solving a problem on TopCoder I used the following assumption. I have n intervals: $ [a_1,b_1], [a_2,b_2],...,[a_n,b_n]$ and a number $T$ such that: $$ a_1 + a_2 + ... + a_n \leq T \leq b_1 + b_2 + ... + b_n $$

Then there is a choice of numbers $x_1,x_2,...,x_n$, with $x_i \in [a_i,b_i] $, such that: $$x_1 + x_2 + ... + x_n = T $$

For example, let's say I have to intervals: [1.6 , 2.3] and [1.7 , 2.7]. If T = 4.5 , with 1.6 + 1.7 < 4.5 < 2.3 + 2.7, then I have 4.5 = 2.2 + 2.3 , with 2.2 belonging to the first interval, and 2.3 to the second. The solution is not unique.

Now, I know that this the claim I stated is pretty obvious and intuitive. One can easily find a greedy algorithm that can find a choice of x's. We can start with $x_1 = a_1, x_2 = a_2, ... , x_n = a_n $, and then increment each x as needed to attain the $T$ value.

For example, I begin with T1 = 1.6 + 1.7 = 3.3. I didn't attain the T value! I look at the first x, and I try to increase it. T2 = 2.3 + 1.7 = 4.0. I haven't reached the T value and I can no more increase the first x. So I proceed to the second x. By increasing the second x to 2.2, I now have 2.3 + 2.2 = 4.5.

Intuitively this algorithm works every time. But how can I prove its correctness? Note that I don't have much experience in proving this type of claim. My 'common sense' got me to this statement. It would be great if somebody could show me how to prove it. Thank you!!

Answer 1

Since Hagen was faster in mentioning the intermediate value theorem, let me prove that your algorithm works. Let $B_k:=\sum_{i=1}^k b_i + \sum_{i=k+1}^na_i$ for $k=0,\dots,n-1$. For example, $B_0 = \sum_{i=1}^na_i\leq T$ - that's your first try. You know that $B_k$ is a non-decreasing sequence and that $T\leq B_{n-1}$. Either $T= B_{n-1}$ which is simple, or $T< B_{n-1}$ hence there exists $j(T)$ such that $B_{j(T)} \leq T\leq B_{j(T)+1} = B_{j(T)}$. Indeed, if such $j(T)$ does not exist you get a contradiction. Recall $$ B_{j(T)+1} = B_{j(T)} + b_{j(T)+1} - a_{j(T)+1} $$ hence $T = B_{j(T)} + c$ for some $c\in [a_{j(T)+1},b_{j(T)+1}]$ which is what you need.

Answer 2

The set $[a_1,b_1]\times \ldots\times [a_n,b_n]$ is connected (as a product of connected sets) and hence the image under the continuous map $[a_1,b_1]\times \ldots \times [a_n,b_n]\to \mathbb R$, $(x_1,\ldots,x_n)\mapsto x_1+\ldots +x_n$ is connnected, so with $a_1+\ldots +a_n$ and $b_1+\ldots +b_n$ it attains also all intermediate points.

Answer 3

To prove the correctness you can use an invariant. This is a statement that holds true throughout the execution of the algorithm.

In your case, the invariant expresses that the partial sum $S$ that you form never exceeds $T$. (When you try to increase some $x_i$, either the sum reaches $T$ and you stop, or $x_i$ reaches its upper bound $b_i$ before.)

So the invariant guarantees that either you have reached $T$ (and you are done), or you can still increase the sum (by increasing the next $x_i$).

A second aspect of the proof is that the solution will be found after a finite number of steps: as long as the sum has not reached $T$, you can increase the next $x_i$. Indeed, $S<T$ implies that you can add a finite amount to the sum, and this is always possible unless all $x_i$ are saturated. But if all $x_i$ are saturated, $S=T=$the sum of all $b_i$.

S= sum of Ai; { S <= T }
i= 1;
while i <= n and S < T:
  { S < T }
  if S + Bi - Ai < T 
    then S+= Bi - Ai; i++; { We saturated Xi and still have S < T}
    else S= S + T - S; { The last increment was T-S > 0, and now S==T }
  i++;
{ When arrived here, we cannot have i>n as this would imply T > sum of Bi }

For completeness, you should also express in the invariant that all $x_j$ for $j<i$ are saturated.

If you really want to gently but rigorously learn how to write proofs of algorithms, this is a must.