Proizvolov's identity explained

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₁<A₂< … <A_N.

Arrange the other subset in decreasing order:

B₁>B₂> … >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 . 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\lei\len\}

and :

\{n+1,n+2,...,2n\}

coincide. Since the numbers

a_i,b_i

are all distinct, it therefore suffices to show that for any

1\lek\len

max\{a_k,b_k\}>n

. Assume the contrary that this is false for some

, and consider

n+1

positive integers

a_1,a_2,...,a_k,b_k,b_k+1,...,b_n

. Clearly, these numbers are all distinct (due to the construction), but they are at most

: a contradiction is reached.

References

External links

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