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.

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 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².

Proof

A slick proof of the identity is as follows. Note that for any $a,b$, we have that :$|a-b|=\max\{a,b\}-\min\{a,b\}$. For this reason, it suffices to establish that the sets $\{\max\{a_{i},b_{i}\}:1\leq i\leq n\}$ and :$\{n+1,n+2,\dots ,2n\}$ coincide. Since the numbers $a_{i},b_{i}$ are all distinct, it therefore suffices to show that for any $1\leq k\leq n$, $\max\{a_{k},b_{k}\}>n$. Assume the contrary that this is false for some $k$, and consider $n+1$ positive integers $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 they are at most $n$: a contradiction is reached.

References

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

External links

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