1.1

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

Choose negative addends, e.g. a = -3 and b = -4.
[math]a + b = -3 + (-4) = -7[/math]
[math]\min(a,b) = \min(-3,-4) = -4[/math]
Since [math]-7 < -4[/math], we have [math]a + b < \min(a,b)[/math].

More generally, [math]a + b < \min(a,b)[/math] is equivalent to
[math]\bigl(a + b < a\bigr) \land \bigl(a + b < b\bigr)[/math],
which simplifies to [math]b < 0[/math] and [math]a < 0[/math]. Hence any pair of negative numbers makes the sum smaller than either addend.


Back to Chapter 1