Proizvolov's identity - Alchetron, The Free Social Encyclopedia

In mathematics, Proizvolov's identity is an identity concerning sums of differences of positive integers. The identity was posed by Vyacheslav Proizvolov as a problem in the 1985 All-Union Soviet Student Olympiads (Savchev & Andreescu 2002, p. 66).

To state the identity, take the first 2N positive integers,

1, 2, 3, ..., 2N − 1, 2N,

and partition them into two subsets of N numbers each. Arrange one subset in increasing order:

A 1 < A 2 < ⋯ < A N .

Arrange the other subset in decreasing order:

B 1 > B 2 > ⋯ > B N .

Then the sum

| A 1 − B 1 | + | A 2 − B 2 | + ⋯ + | A N − B N |

is always equal to N².

Example

Take for example N = 3. The set of numbers is then {1, 2, 3, 4, 5, 6}. Select three numbers of this set, say 2, 3 and 5. Then the sequences A and B are:

A₁ = 2, A₂ = 3, and A₃ = 5; B₁ = 6, B₂ = 4, and B₃ = 1.

The sum is

| A 1 − B 1 | + | A 2 − B 2 | + | A 3 − B 3 | = | 2 − 6 | + | 3 − 4 | + | 5 − 1 | = 4 + 1 + 4 = 9 ,

which indeed equals 3².

References

Proizvolov's identity Wikipedia

(Text) CC BY-SA