# Solution to puzzle 104: An arbitrary sum

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 n and bi n.  Then
a1, a2, ... , ai n (since a1 < a2 < ... < ai), and
bi, bi+1, ... , bn 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.