Skip to main content.

Solution to puzzle 104: An arbitrary sum

Skip restatement of puzzle.The first 2n positive integers are arbitrarily divided into two groups of n numbers each.  The numbers in the first group are sorted in ascending order: a1 < a2 < ... < an; the numbers in the second group are sorted in descending order: b1 > b2 > ... > bn.

Find, with proof, the value of the sum |a1 − b1| + |a2 − b2| + ... + |an − bn|.


One proof is based upon the observation that, for each i, i = 1, ..., n, one of the numbers ai, bi, belongs to {1, 2, ... , n} while the other belongs to {n+1, n+2, ... , 2n}.

Suppose, to the contrary, that, for some i, ai less than or equal to n and bi less than or equal to n.  Then
a1, a2, ... , ai less than or equal to n (since a1 < a2 < ... < ai), and
bi, bi+1, ... , bn less than or equal to n (since bi > bi+1 > ... > bn).
Hence the n + 1 distinct numbers, a1, a2, ... , ai, bi, bi+1, ... , bn, belong to {1, 2, ... , n}; a contradiction.

A very similar contradiction is reached if we assume that, for some i, ai > n and bi > n.
We conclude that, for each i, i = 1, ..., n, exactly one of the numbers, ai, bi, belongs to {1, 2, ... , n} while the other belongs to {n+1, n+2, ... , 2n}.

For each summand, |ai − bi|, we may if necessary swap ai, bi, so that the smaller number is subtracted from the larger number, and then drop the modulus sign.  This leaves the value of the summand unchanged.  It then follows that

|a1 − b1| + |a2 − b2| + ... + |an − bn| = [(n+1) + (n+2) + ... + 2n] − [1 + 2 + ... + n]
  = [(n+1) - 1] + [(n+2) - 2] + ... + [(n+n) - n]
  = n + n + ... + n
  = n2

Remarks

This result is known as [Java] Proizvolov's Identity.

Source: Mathematical Miniatures, by Svetoslav Savchev and Titu Andreescu. See Chapter 18.

Back to top