60-odd years of moscow mathematical

that depends on a positive integer n ≥ n
0
. We believe S(n) to be true for any positive integer n ≥ n
0
if
1
Although every cultured person must know these facts, among other useless data, some people do not; therefore, we
recommend to skim through this section before advancing further.
2
Kanel-Belov A., Kovaldzhi A., Vasilev N. Preparatory Problems to LVII Moscow Mathematical Olympiad, Treade,
Moscow, 1994.
3
Some mathematicians with quite unorthodox minds doubt the universality of this principle. They only believe in the
numbers we can actually count. Since the mathematics obtained this way is supposed to be very poor, these ideas are not
popular. They did not die out, however, because the attempts to consider only constructible statements clarified some messy
or nonconstructive proofs of interesting theorems.
11

---

12
INTRODUCTION
1) S(n
0
) holds for some n
0
;
2) the validity of S(l) for k ≥ l implies S(k − 1).
Warning. It could happen that the inductive step is easy to perform but the conclusion is nevertheless
wrong. This happens if the justification of the base of the induction is ignored and we are trying to prove a
wrong statement.
Example: Let us “prove” that The eyes of all people are of the same color. Indeed, the eyes of one
person are of the same color
1
. Now, assume that the statement is true for k people; then it is obviously true
for k + 1 people since any k of these k + 1 persons have the eyes of the same color. The catch is that for
k = 2 the statement is generally false.
Games: selected ideas. 1) Solution backwards, cf. Problems ...
2) Correspondence. The presence of a lucky move can be justified by a symmetry, partition into pairs
or a complement, cf. Problems ...
3) Transfer of the move. If we can use the opponent’s strategy we are not worse off than the opponent.
For example we win or draw if we can assume the opponent’s winning position at will, cf. Problems...
4) “Prepared homework” (on an infinite field), cf. Problems
Selected ideas. Reductio ad absurdum. If we assume that the statement to prove is false and deduce
a contradiction from this assumption, this will prove that the statement was true after all.
Estimates. We estimate a complicated quantity with a simpler one. The inequality between the mean
arithmetic and the mean geometric is often used.
An invariant. A quantity is sometimes always even (odd) or just a constant. This implies that a situation
in which this quantity is odd (even) or not a constant are impossible, cf. Problems ... Sometimes a quantity
can be calculated (or estimated) in two ways and we compare the results, cf. Problems A residue can serve
as an invariant and we only have to check the possibilities case-by-case, cf. Problems ...
Cycles or periods that arise in a process are examples of invariants, cf. Problems ...
The rule of an extreme element. Singular or extreme objects (the largest nummer, the nearest point, the
vertex of a polygon, the degenerate circle, the limit case, etc.) often clarify the regular case. Cf. Problems
...
Standard common notations. In all problems on tournaments it is assumed that each participant
competes with every other only once. In a chess tournament, a player gets 1 point for victory, half a point
if the game ends in a draw, and 0 for loss; in soccer, all scores are twice as much. In basketball, tennis, etc.,
there are no draws.
The main diagonal (of a square array, or a table, or a matrix) is the one which connects the top left
corner with the bottom right corner while the other longest diagonal is called the side diagonal. Dimensions