Cut the knot: learn to enjoy mathematics
A math books store at a unique math study site. Learn to enjoy mathematics.
Google
Web CTK
Terms of use
Privacy Policy

More Mathematics
CTK Exchange

Games to Relax
Guest book
Recommend this site

Sites for teachers
Sites for parents

Manifesto: what CTK is about Buying a book is a commitment to learning Things you can find on CTK Email to Cut The Knot Recommend this page

Proizvolov's Identity

At the beginning, the applet displays 2N natural numbers: 1, 2, 3, ., 2N - 1, 2N. Select any N numbers by clicking on N numbers in turn. The selected numbers will be arranged in a column on the left in the decreasing order. The remaining N numbers will be arranged in the increasing order on the right.

<hr> <h3> This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet. </h3> <hr>

Thus the set of numbers N2N = {1, 2, 3, ., 2N - 1, 2N} is split into two sequences, one decreasing and one increasing:

  a1 > a2 > a3 > . > aN and
b1 < b2 < b3 < . < bN.

The applet is supposed to suggest a theorem due to V. Proizvolov, a well known Russian mathematician:

  |a1 - b1| + |a2 - b2| + . + |aN - bN| = N2.

The proof is based on the observation that for every i, i = 1, ., N, one of the numbers in the pair ai, bi belongs to NN = {1, 2, ., N}, the other to NN+1, 2N = {N+1, N+2, ., 2N}.

Assume on the contrary, that, for example, that, for some i, both numbers in the pair belong to NN:

(1) ai < N + 1
bi < N + 1.

This would imply that (together with ai) there are in the very least (N - i + 1) of the sequence {a} that are below N + 1. There also would be at least i terms from the second sequence {b} below N + 1. Together this would give N + 1 distinct natural numbers less than N + 1. But there are only N of them; thus our assumption (1) led to a contradiction.

The case

(2) ai > N
bi > N.

leads to a contradiction in a similar manner. Thus indeed, in any pair ai, bi one number belongs to NN, the other to NN+1, 2N. This implies that

 
|a1 - b1| + |a2 - b2| + . + |aN - bN|= [(N+1) + (N+2) + . + 2N] - [1 + 2 + . + N]
 = [1 + 2 + . + 2N] - 2·[1 + 2 + . + N]
 = N(2N + 1) - N(N + 1)
 = N2.

References

  1. S. Savchev, T. Andreescu, Mathematical Miniatures, MAA, 2003, p. 66.

Copyright © 1996-2008 Alexander Bogomolny



Search:
Keywords: