In EWD1140 we proved that the arithmetic mean is at least the geometric mean; in EWD1171 we returned to that problem, including most of the heuristics. One rabbit, though, remained: the choice of c between x and y so that
(0) x,y := c, x+y−c
will decrease the distance between x and y. I know why the rabbit remained: in my first effort I hit upon a case analysis too ugly to include in my text, and so the coward waved his hands. (The case analysis was generated by the value of x < y before and after.)
All this was a little bit stupid (and dishonest, but that is another story) since the whole argument —see the opening sentence of EWD1140— is built on the identity
(x+y) = (x−y) + 4xy
and instead of worrying about decreasing the distance between x and y, we should focus our attention to decreasing (x−y).
The following simple calculation massages the initial condition under which (0) decreases (x−y) :
(c − (x+y−c)) < (x−y)
= {algebra}
(2c−x−y) < (x−y)
= {algebra: a < b+c ≡ a−b < c}
(2c−x−y) − (x−y) < 0
= {algebra: a−b = (a−b)(a+b)}
(2c−2x)(2c−2y) < 0
= {algebra}
(c−x)(c−y) < 0
which compactly and without case analysis characterizes the situation in which c lies between x and y.
For the modification chosen in EWD1171:
(1) x,y := c, x y/c
the analogous calculation leads to
(c−x)(c−y) < 0 ,
which is only equivalent to (c −x)(c−y) < 0 if (c+x)(c+y) > 0. The whole problem is in terms of positive numbers, so this condition is satisfied. The observation, however, confirms my impression that the choice of (0) in EWD1140 —i.e. increasing the product under constant sum— is to be preferred over the choice of (1) in EWD1171 —i.e. decreasing the sum under constant product—.
Austin, 15 February 1995
PS The algebra on the previous page is somewhat elaborate. It just shows how one is affected by lecturing for American undergraduates.
prof.dr. Edsger W.Dijkstra
Department of Computer Sciences
The University of Texas at Austin
Austin, TX 78712-1188
USA