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.

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

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

The proof is based on the observation that for every i, i = 1, ..., N, one of the numbers in the pair a_i, b_i belongs to N_N = {1, 2, ..., N}, the other to N_{N+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 N_N:

This would imply that (together with a_i) 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

leads to a contradiction in a similar manner. Thus indeed, in any pair a_i, b_i one number belongs to N_N, the other to N_{N+1, 2N}. This implies that

References

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

Copyright © 1996-2008 Alexander Bogomolny