60-odd years of moscow mathematical

· p
2
· · · · · p
n−1
· p
n
and set
f (k) = p
1
+ p
2
+ · · · + p
n−1
+ p
n
+ 1. We perform the same operation f with f (k), and so on. Prove that
the resulting sequence of numbers k, f (k), f (f (k)), . . . eventually becomes a periodic one.
36.1.10.2. See Problem 36.1.9.1.
36.1.10.3. At some integer points a polynomial P (x) with integer coefficients takes values 1, 2 and 3.
Prove that there exists not more than one integer at which the polynomial is equal to 5.
36.1.10.4. Prove that every convex polyhedron has two faces with the same number of sides.
36.1.10.5. A control panel of N switches and a board with N bulbs are on the sides of a “black
box”. By switching consecutively all possible combinations of the switches we consecutively light all possible
combinations of the bulbs. The state of the panel of lights directly depends on the state of the switches on
the control panel. It is known that when one switch is flipped, exactly one bulb lights up or goes off. Prove
that the state of each bulb depends on exactly one switch (for every bulb its own switch).
Tour 36.2
Grade 7
36.2.7.1. A four-digit number is subtracted from a number composed of the same digits in reverse order.
Can the difference be equal to 1008?
36.2.7.2. Consider an acute triangle ABC and discs centered at the vertices of the triangle with their
radii equal to heights dropped from respective vertices. Prove that every point of the triangle is covered by
at least one disc.
36.2.7.3. A 100 × 100 piece of graph paper is painted 100 different colors. Every unit square of the grid
is either painted one of the colors or not painted at all. A coloring will be called regular if no column and no
row has two squares of the same color. Is it possible to paint this piece of paper regularly so that all squares
are painted if initially there are a) 100
2
− 1; or b) 100
2
− 2; or c) 100 regularly painted squares?
36.2.7.4. See Problem 36.2.8.3 a) below.
Grade 8
36.2.8.1. There is an ink blot on a piece of paper. For every point of the blot consider its minimal and
the maximal distance to the boundary of the blot. The greatest of all minimal distances and the least of
all maximal distances are selected and compared. What is the shape of the blot if these two numbers are
equal? (See Fig. 81)
Figure 81. (Probl. 36.2.8.1)
36.2.8.2. See Problem 36.2.7.3 replacing 100 with an arbitrary n.
36.2.8.3. At the center of a square stands a cop and at one of the square’s vertices stands a robber.
The Rule allows the cop to run anywhere in the square and even digress outside its limits, while the robber
can only move along the square’s sides. For each of the following ratios of the cop’s top speed to that of the
robber a) 1/2; b) 0.49; c) 0.34; d) 1/3, prove that the cop can run so as to be on the same side as the robber
at some moment.
36.2.8.4. Prove that it is possible to place an equilateral triangle into a convex equilateral (but not
necessarily regular) pentagon, with sides equal to the sides of the triangle, so that they have one side in
common and the entire triangle is inside the pentagon.

---

108
MOSCOW MATHEMATICAL OLYMPIADS 1 – 59
Grade 9
36.2.9.1. The decimal expression of a 100-digit number consists of 1’s and 2’s. The Rule allows one to
select arbitrarily 10 consecutive digits of which the first five may change places with the second five. Two
numbers will be called similar if one can be obtained from the other one in several such operations. What
greatest number of such 100-digit numbers can be selected so no two of them are similar?
36.2.9.2. A closed non-selfintersecting broken line is drawn on an infinite chessboard along the sides
of its squares. There are K black squares inside the broken line. What is the greatest area of the figure
bounded by the broken line?
36.2.9.3. See Problem 36.2.10.1 for m = 5.
36.2.9.4*. Two 1’s are situated at the endpoints of a line segment. The first move is to insert their
sum — the number 2 — between them. Next move is to insert between every two adjacent numbers their
sum, and so on, 1 000 000 times; see Fig. 82. How many times will the number 1973 be written during this
process?
Figure 82. (Probl. 36.2.9.4)
36.2.9.5*. See Problem 36.2.8.3. Let the robber’s top speed be 2.9 times that of the cop. Is it possible
for the cop to arrive on the same side with the robber?