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 < ⋯ < A N . {\displaystyle A_{1}<A_{2}<\cdots <A_{N}.}
Arrange the other subset in decreasing order:
B 1 > B 2 > ⋯ > B N . {\displaystyle B_{1}>B_{2}>\cdots >B_{N}.}
Then the sum
| A 1 − B 1 | + | A 2 − B 2 | + ⋯ + | A N − B N | {\displaystyle |A_{1}-B_{1}|+|A_{2}-B_{2}|+\cdots +|A_{N}-B_{N}|}
is always equal to N2.
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:
A1 = 2, A2 = 3, and A3 = 5; B1 = 6, B2 = 4, and B3 = 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 , {\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 32.
Proof For any a , b {\displaystyle a,b} , we have: | a − b | = max { a , b } − min { a , b } {\displaystyle |a-b|=\max\{a,b\}-\min\{a,b\}} . For this reason, it suffices to establish that the sets { max { a i , b i } : 1 ≤ i ≤ n } {\displaystyle \{\max\{a_{i},b_{i}\}:1\leq i\leq n\}} and : { n + 1 , n + 2 , … , 2 n } {\displaystyle \{n+1,n+2,\dots ,2n\}} coincide. Since the numbers a i , b i {\displaystyle a_{i},b_{i}} are all distinct, it suffices to show that for any 1 ≤ k ≤ n {\displaystyle 1\leq k\leq n} , max { a k , b k } > n {\displaystyle \max\{a_{k},b_{k}\}>n} . Assume the contrary that this is false for some k {\displaystyle k} , and consider n + 1 {\displaystyle n+1} positive integers a 1 , a 2 , … , a k , b k , b k + 1 , … , b n {\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 n {\displaystyle n} of them, which is a contradiction.
Notes
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