60-odd years of moscow mathematical

n = 3k + 2 ≥ 2 : (2, 1), (3, 3), (5, 4), (6, 6), . . . (n − 2, n − 2)
n = 3k + 1 ≥ 4 : (2, 1), (1, 2), (4, 3), (5, 5), (7, 6), . . . (n − 2, n − 2)
n = 3k
≥ 6 : (2, 1), (1, 2), (3, 2), (4, 4), (6, 5), (7, 7), . . . (n − 2, n − 2)
A singular case: n = 3. A case-by-case verification shows that in this case there exists no closed routes; but
it is not difficult to construct a route with the beginning point and endpoint on the opposite sides of one
road; see Fig. 120 b).
Figure 120. (Sol. A65)
Figure 121. (Sol. A66)

---

178
SOLUTIONS
66. If the midpoints of the parallel sides in an octagon are connected with straight lines, these lines pass
through the center O of the circle. Introduce the following notations, see Fig. 121:
x = 12
˘
A
1
A
2
,
z = 12
˘
A
2
A
3
,
v = 12
˘
A
3
A
4
,
y = 12
˘
A
5
A
6
,
t = 12
˘
A
6
A
7
,
w = 12
˘
A
7
A
8
.
Since x + z = t + y and z + v = t + w (two pairs of vertical angles as shown on Fig. 121), it follows that
x − v = y − w and x + w = y + v. Therefore,
t + 2w + 2x + z = t + 2y + 2v + z,
i.e., line l connecting the midpoints of
˘
A
2
A
3
and
˘
A
6
A
7
cuts off the same sum of the arcs on the half-circles.
Since
˘
A
1
A
8
and
˘
A
4
A
5
supplement these sums to half-circles,
˘
A
1
A
8
=
˘
A
4
A
5
implying A
1
A
8
= A
4
A
5
,
Q.E.D.
69. a) For example, take for such numbers all n-digit numbers of the form 11...11, where n is a power
of 3.
b) Let S(N ) = 2
n
− 1 and let the number consisting of n last digits of N be divisible by 2
n
; then N is
also divisible by 2
n
. For example, N = 92112 is divisible by 16.
71. Let f (x) 6= 0. Then
f (x − 2y) + f (x) = 2f (x − y)g(y),
f (x) + f (x + 2y) = 2f (x + y)g(y)
implying
f (x − 2y) + f (x + 2y) = −2f (x) + 2g(y)(f (x − y) + f (x + y)) = f (x)(−2 + 4g(y)
2
).
On the other hand,
f (x − 2y) + f (x + 2y) = 2f (x)g(2y).
Dividing by f (x) we get g(2y) = −1 + 2g(y)
2
> −1. Since 2y is an arbitrary number, we are done.
Remark. For example, the functions f (x) = sin x, g(y) = cos y possess the property. Accordingly, we
have cos y > −1.
73. First, suppose that all roots of the polynomial P can be divided into pairs of complex-conjugate
non-real numbers, z
i
and ¯
z
i
, as follows:
P (x) = [(x − z
1
) . . . (x − z
n
)][(x − ¯
z
1
) . . . (x − ¯
z
n
)] = P
1
(x)P
2
(x),
where P
1
(x) = (x − z
1
) . . . (x − z
n
); P
2
(x) = (x − ¯
z
1
) . . . (x − ¯
z
n
).
Then P
2
(x) = P
1
(x). Denote: P
1
(x) = Q(x) + iR(x), P
2
(x) = Q(x) − iR(x), where Q and R are
polynomials with real coefficients. We get
P (x) = P
1
(x)P
2
(x) = Q(x)
2
+ R(x)
2
.
Now, let us turn to the general case and remember that any real polynomial can be expressed in the
form
P (x) = a(x − x
1
)
k
1
. . . (x − x
s
)
k
s
˜
P (x),
where a 6= 0 is the coefficient of the highest term, x
1
, . . . , x
k
all distinct real roots of P (x), ˜
P (x) a polynomial
without real roots, i.e., ˜
P (x) is the product of quadratic polynomials (x−z)(x− ¯
z) = x
2
+px+q. If P (x) ≥ 0
for some x ≥ 0 (e.g. for x > x
j
, 1 ≤ j ≤ s) then a > 0.
Then, a = b
2
, b > 0 and by the already proven ˜
P (x) = ˜
Q(x)
2
+ ˜
R(x)
2
. Suppose all k
j
are even. Then
P (x) = b
2
Q
2
1
(x) ˜
P (x) = (bQ
1
˜
Q)(x)
2
+ (bQ
1
˜
R)(x)
2
and we are done. Now it suffices to prove that all k
j
are
indeed even.
It remains, moreover, to consider only one case: P (x) = (x − x
1
) . . . (x − x
s
) with distinct roots. To
conclude the proof show that P (x
0
) < 0 for a real x
0
.
74. Let x be not divisible by 3. Then x
2
≡ 1 (mod 3) implying 2y
2
≡ 1 (mod 3). But this means that
y
2
≡ 2 (mod 3) which is impossible. Therefore, x is divisible by 3, hence so is y. But then the left hand
side is divisible by 9 and dividing by 3 we see that 2t
2
− z
2
is divisible by 3. Hence, both t and z should
be divisible by 3 by the same reasons. Thus, any solution (x, y, z, t) has a common divisor 3. This easily
implies that the only solution is
x = y = z = t = 0.

---

SOLUTIONS TO SELECTED PROBLEMS OF MOSCOW MATHEMATICAL CIRCLES
179
75. a) Denote the position of the airplane at the moment t by X(t) and let the whole time of the flight
be T sec. Then X(0) = Γ
1
, X(T ) = Γ
2
, where 0 ≤ t ≤ T , T > 1.
Denote:
α(t) = ∠X(t)AX(t + 1),
β(t) = ∠X(t)BX(t + 1).
Since the path of the plane is continuous, so are the functions α(t) and β(t) defined for 0 ≤ t ≤ T − 1.
Let us draw a plane through Γ
1
Γ
2
and X(1). From Fig. 122 a) we see that α(0) > β(0) because α(0) is
an exterior angle and β(0) is an interior angle of 4AX(1)B.
Similarly, by drawing the plane through Γ
1
Γ
2
and X(T − 1), we deduce from 4AX(1)B that α(T − 1) <
β(T − 1). Then the continuity of α(t) and β(t) implies the existence of a moment t
0
such that α(t
0
) = β(t
0
),
Q.E.D.
b) Fig. 122 b) shows a half-circle of diameter Γ
1
B (the whole picture is two-dimensional); Γ
2
lies on
the half-circle near B and A belongs to the diameter near Γ
1
. Then β =
1
2
˘
XY and α >
1
2
˘
XY , since
α =
1
2
˘
XY +
˘
X
0
Y
0
, where X
0
and Y
0
are the intersection points of XA and Y A, respectively, with the
second part of the circle. Therefore, α(t) > β(t) for all t.
Figure 122. (Sol. A75)
76. Let us assume that the shades are closed, i.e., the boundary of a shade is a part of the shade. (If
the shades are open the same proof is applicable with slight modifications.)
Assume that the statement of the problem is false and quadrilateral ABCD with discs K
A
, K
B
, K
C
,
K
D
is a counterexample. We may assume that the discs are in general position, i.e., are not tangent to each
other, no 3 of them intersect at one point and the pair-wise intersection points do not lie on the sides and
diagonals of the quadrilateral; otherwise — i.e., for a singular position — we can slightly enlarge the discs
without violating the nature of the counterexample.
Let us prove that the system of discs indicated should possess the following properties:
1
◦
. No three discs have a common point. Indeed, if, say, K
A
, K
B
and K
C
have a common point, they
cover 4ABC.
2
◦
. The points of pair-wise intersection of circles (the boundaries of discs K
A
, . . . , K
D
) cannot lie inside
ABCD. Indeed, if such a point would have existed, it would have been covered by one more disc (in order
to exclude the possibility of a lighted spot in its neighborhood). This contradicts property 1
◦
.
3
◦
. None of the discs can intersect two other discs. Indeed, if, say, K
A
intersects K
B
and K
C
, then
the lighted (after K
D
is deleted) part of 4ABC can not intersect segments AB and AC and can not have
vertices inside 4ABC (by property 2
◦
). It is not difficult to observe that this is impossible.
The discs with centers at the vertices of the quadrilateral possessing property 3
◦
can not, however, cover
the whole quadrilateral. The contradiction obtained proves the statement of the problem.
77. On the line, introduce a coordinate system so that at the Beginning of Time, simply called initial
moment, one bacterium, call it F for first, were in the origin. It survives at the next moment only if there is
a bacterium in one of the points: (with coordinates) −1 or
√
2. These bacteria, in their turn, survive only
if at the initial moment there were bacteria at points −2, −1 +
√
2 or 2
√
2. And so on.
Consider all the bacteria that at the initial momets occupied points with coordinates −n + m
√
2 for
positive integer n, m. Since the total number of all bacteria is finite, there finitely many such chosen bacteria.
So there is one bacterium with the maximal m. If there are several such species, take the left-most of them,
corresponding to the greatest value of n; call it B.
It is clear now that there are no bacteria at points −(n + 1) + m
√
2 and −n + (m + 1)
√
2 and bacterium
B is doomed to inevitable death.
Now it is not difficult to see that all the bacteria living at points with coordinates −k + m
√
2 for all k
will eventually die out, too.

---

180
SOLUTIONS
Now apply the inverse induction on m to see that in the end bacterium F will also perish. Since it was
chosen at random (we could have shifted the origin), the statement is proved.
78. Let a k-configuration C(k) be an arrangement of a finite number of points such that there exists at
least k points at distance 1 from any of the points.
Take a k-configuration and move it a a solid body by a vector of length 1 so that none of the points
thus moved coincide with any of the initial points of the configuration. The new set of points, the union of
the initial ones and the moved ones, clearly constitute a (k + 1)-configuration. The endpoints of a segment
of length 1 is a 1-configuration; a 1000-configuration contains 2
1000
points — the projections of the vertices
of a 1000-dimensional unit cube onto a two-dimensional plane.
Let us try to find a configuration of points with the number of points < 2
1000
. Denote by A + B the
vector sum of A and B — the set of all pairwise sums of points from A and B (each point being identified
here with the endpoints of the vector equal to the sum of the two vectors corresponding to the summands).
Clearly, if A has m points and B has n points then A + B has no more than m · n points.
Let |C(k)| be the minimal possible number of points in a k-configuration C(k). Let us prove that
|C(m + n)| ≤ |C(m)| · |C(n)|.
Consider any point a