Proizvolov's identity

Short description: On sums of differences between 2 equal sets that partition the first 2N positive integers

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:

[math]\displaystyle{ A_1 \lt A_2 \lt \cdots \lt A_N. }[/math]

Arrange the other subset in decreasing order:

[math]\displaystyle{ B_1 \gt B_2 \gt \cdots \gt B_N. }[/math]

Then the sum

[math]\displaystyle{ |A_1-B_1| + |A_2-B_2| + \cdots + |A_N-B_N| }[/math]

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

[math]\displaystyle{ |A_1-B_1| + |A_2-B_2| + |A_3-B_3| = |2-6| + |3-4| + |5-1| = 4+1+4 = 9, }[/math]

which indeed equals 3².

Proof

A slick proof of the identity is as follows. Note that for any [math]\displaystyle{ a,b }[/math], we have that :[math]\displaystyle{ |a-b|=\max\{a,b\}-\min\{a,b\} }[/math]. For this reason, it suffices to establish that the sets [math]\displaystyle{ \{\max\{a_i,b_i\}:1\le i\le n\} }[/math] and :[math]\displaystyle{ \{n+1,n+2,\dots,2n\} }[/math] coincide. Since the numbers [math]\displaystyle{ a_i,b_i }[/math] are all distinct, it therefore suffices to show that for any [math]\displaystyle{ 1\le k\le n }[/math], [math]\displaystyle{ \max\{a_k,b_k\}\gt n }[/math]. Assume the contrary that this is false for some [math]\displaystyle{ k }[/math], and consider [math]\displaystyle{ n+1 }[/math] positive integers [math]\displaystyle{ a_1,a_2,\dots,a_k,b_k,b_{k+1},\dots,b_n }[/math]. Clearly, these numbers are all distinct (due to the construction), but they are at most [math]\displaystyle{ n }[/math]: a contradiction is reached.

References

• Savchev, Svetoslav; Andreescu, Titu (2002), Mathematical miniatures, Anneli Lax New Mathematical Library, 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