Proizvolov's identity

This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles. (June 2016)

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.^[1]

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:

${\displaystyle A_{1}<A_{2}<\cdots <A_{N}.}$

Arrange the other subset in decreasing order:

${\displaystyle B_{1}>B_{2}>\cdots >B_{N}.}$

Then the sum

${\displaystyle |A_{1}-B_{1}|+|A_{2}-B_{2}|+\cdots +|A_{N}-B_{N}|}$

is always equal to N².

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

${\displaystyle |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².

For any ${\displaystyle a,b}$, we have: ${\displaystyle |a-b|=\max\{a,b\}-\min\{a,b\}}$. For this reason, it suffices to establish that the sets ${\displaystyle \{\max\{a_{i},b_{i}\}:1\leq i\leq n\}}$ and :${\displaystyle \{n+1,n+2,\dots ,2n\}}$ coincide. Since the numbers ${\displaystyle a_{i},b_{i}}$ are all distinct, it suffices to show that for any ${\displaystyle 1\leq k\leq n}$, ${\displaystyle \max\{a_{k},b_{k}\}>n}$. Assume the contrary that this is false for some ${\displaystyle k}$, and consider ${\displaystyle n+1}$ positive integers ${\displaystyle a_{1},a_{2},\dots ,a_{k},b_{k},b_{k+1},\dots ,b_{n}}$. Clearly, these numbers are all distinct (due to the construction), but there are at most ${\displaystyle n}$ of them, which is a contradiction.

• Savchev, Svetoslav; Andreescu, Titu (2002), Mathematical miniatures, Anneli Lax New Mathematical Library, vol. 43, Mathematical Association of America, ISBN 0-88385-645-X.

• Proizvolov's identity at cut-the-knot.org
• A video illustration (and proof outline) of Proizvolov's identity by Dr. James Grime