Proizvolov's identity

From Wikipedia, the free 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 < \cdots < A_N.

Arrange the other subset in decreasing order:

 B_1 > B_2 > \cdots > B_N.

Then the sum

 |A_1-B_1| + |A_2-B_2| + \cdots + |A_N-B_N|

is always equal to N2.

[edit] 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:

A1 = 2, A2 = 3, and A3 = 5;
B1 = 6, B2 = 4, and B3 = 1.

The sum is

| A1B1 | + | A2B2 | + | A3B3 | = | 2 − 6 | + | 3 − 4 | + | 5 − 1 | = 4 + 1 + 4 = 9,

which indeed equals 32.

[edit] References

  • Savchev, Svetoslav & Andreescu, Titu (2002), Mathematical miniatures, vol. 43, Anneli Lax New Mathematical Library, Mathematical Association of America, ISBN 088385645X .

[edit] External links