Proizvolov's identity

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 harv|Savchev|Andreescu|2002|p=66.

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

:1, 2, 3, ..., 2"N" − 1, 2"N",

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

:

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 "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"_"3" = 5;:"B"₁ = 6, "B"₂ = 4, and "B"_"3" = 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

*.

External links

* [http://www.cut-the-knot.org/Curriculum/Games/ProizvolovGame.shtml Proizvolov's identity] at cut-the-knot.org