Misplaced Pages

Proizvolov's identity

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
On sums of differences between 2 equal sets that partition the first 2N positive integers
This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (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.

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 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:

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

Proof

A slick proof of the identity is as follows. Note that for any a , b {\displaystyle a,b} , we have that : | 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 therefore 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 they are at most n {\displaystyle n} : a contradiction is reached.

Notes

  1. Savchev & Andreescu (2002), p. 66.

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

Categories: