60-odd years of moscow mathematical

Part 1: Problems

---

---

Introduction
Prerequisites and notational conventions
The following prerequisites were largely assumed to be known to any participant of an Olympiad.
1
Lately it became clear
that the gap between the standard school mathematics and that of an Olympiad should be bridged in order not to discriminate
against an average student. For example, the collection
2
of preparatory problems for the jubilee 57-th Olympiad contained
several very useful comments partly coinciding with ours. We borrowed some of them.
We expect that the reader of knows how to plot the graph of the function y = ax
2
+ bx + c given the coefficients a, b, c.
Various (good) books on elementary mathematics written in English use different notations, e.g., quadrangle — quadri-
lateral; cathetus — leg, etc. To augment the confusion the original problems for various Olympiads were compiled by different
authors, each with the own style.
We edited the text in order to reduce such discrepancies but to please all was impossible. For example, the requirements
of present AMS mathematics editors to style are sometimes at variance with Webster’s dictionaries and differ from guidelines
formerly advocated by AMS via Halmos’s pamphlet“How to write mathematics”, originally published in L’Enseignements
Math´ematiques t.XVI, fasc. 2, 123–152 and reprinted many times since then in many languages.
Problems are enumerated as follows: the first number is the number of the Olympiad, the second one
is the number of the tour (if there was only one tour this number is skipped), the third number is that of
the grade, and the fourth number is the number of the problem itself. There are natural modifications of
these notations, e.g. 1.2.C.1 denotes Olympiad 1, tour 2, set C, Problem 1; 4.2.2 denotes Olympiad 4,
tour 2, Problem 2; 10.2.7-8.3 denotes Olympiad 10, tour 2, grades 7-8, Problem 3; in 33.D.7.4 D is for
Pythagoras’ Day.
An asterisk marks a more difficult (heading of a) problem, e.g., 1.2.C.1 b)*.
The principles. Dirichlet’s principle. If n rabbits sit in k hutches, then there is a hutch with not
less than
n
k
rabbits and a hutch with not more than
n
k
rabbits.
Though this principle is obvious, it sometimes solves difficult problems: it is not always easy to select
objects that play the role of rabbits and hutches.
The Dirichlet’s principle applies to continuous quantities as well: If n rabbits have eaten k kg of food,
then there is a rabbit who has eaten not less than
n
k
kg and a rabbit who has eaten not more than
n
k
kg.
The principle of mathematical induction is used to prove an infinite sequence of statements:
Consider a statement S(n) 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) S(n
0
) holds for some n
0
;
2) the validity of S(l) for n
0
≤ l ≤ k implies S(k + 1).
Heading 1) is called the base of induction; heading 2) is called the inductive step and the assumption we
use in 2) the inductive hypothesis
3
.
Example: Find the sum 1 + 3 + ... + (2n − 1).
Solution. Let us denote this sum by S(n) and look at it for small n. We see that S(1) = 1, S(2) = 4,
and S(3) = 9. An educated guess is: S(n) = n
2
.
The base of induction is fulfilled for n
0
= 1.
Now the inductive step: S(k + 1) = S(k) + 2(k + 1) − 1 = (by the inductive hypothesis) = k
2
+ 2k + 1 =
(k + 1)
2
. Q.E.D.
Sometimes the induction is used backwards, cf. Problem 20.2.10.5. Namely, Consider a statement S(n)