60-odd years of moscow mathematical

|OH
−→
p
|
cos(OH
−→
p
, OK
−→
)
=
|OP
−→
|
|OK
−→
|
>
|OP
−→
|
|OR
−→
|
= |OP
−→
|
1
|OH
−→
q
|
cos(OH
−→
qp
, OK
−→
) = |OP
−→
| |~e
p
| cos(~v, ~e
q
) = cos(~v, ~e
q
).
Now, let us introduce a function f
σ
(N ) that depends on the point N of the plane and on the distribution
σ of searchlights over the points M
1
, . . . , M
n
:
f
σ
(N ) = M
1
N
−−→
· ~e
σ(1)
+ M
2
N
−−→
· ~e
σ(2)
+ . . . + M
n
N
−−−→
· ~e
σ(n)
,
(∗)
1
If we leave out the 3-dimensional generalization for better days, the following solution can be considerably simplified by
assuming that all OA
i
are of unit length.

---

SOLUTIONS TO SELECTED PROBLEMS OF MOSCOW MATHEMATICAL CIRCLES
163
where σ(i) is the number of the searchlight placed at point M
i
.
Lemma 2. If point N is not lighted up under the arrangement σ of the searchlights, there is an
arrangement τ of searchlights such that f
τ
(N ) > f
σ
(N ).
Proof. First, we give an algorithm to improve the arrangement σ.
Algorithm. Let all searchlights α
i
first stand at points M
i
with the same index. Let α
1
not light up N .
Remove it for a while and place at point M
1
the searchlight which does illuminate N . (Explain yourselves
why such a searchlight will certainly be found.)
Let it be α
2
. Now, there is nothing at point M
2
, where α
2
used to be. Out of the remaining searchlights,
place at M
2
the one which will light N . Let it be α
3
. Then we place the searchlight α
4
at M
3
to light N ,
the searchlight α
5
at M
4
, and so on, until we have a cycle, see Fig. 109 e).
Figure 109. (Sol. A14)
This means that the searchlight α
k+1
is moved over to M
k
, the searchlight α
k+2
is moved to M
k+1
, etc.,
and α
k
to M
s
, where s > k. Bring back all searchlights α
1
, . . . , α
k−1
which did not get into the cycle to
their initial points M
1
, M
2
, . . . , M
k−1
.
The result of the application of the algorithm is that N is lighted up by each searchlight α
k
, α
k+1
, . . . α
s
,
where s ≥ k + 1, because N was not lighted up before.
Let us see how f (N ) changed under the application of the algorithm. The summands with the index
of M
i
not equal to k, k + 1, . . . , s in the sum (∗) did not change, whereas, as follows from Lemma 1, the
summands with the indices k, k + 1, . . . , s increased. Q.E.D.
However, f
σ
cannot be directly used yet to evaluate the “quality” of the arrangement σ since it depends
on N . The situation is saved by the wonderful
Lemma 3. For any two points N
1
and N
2
, the difference f
σ
(N
1
) − f
σ
(N
2
) does not depend on the
arrangement of searchlights.
Proof. Observe that the sum
n
P
i=1
e
σ(i)
−−→ does not depend on the choice of an arrangement; therefore,
f
σ
(N
1
) − f
σ
(N
2
) =
n
P
i=1
M
σ(i)
N
1
−−−−−→
· e
σ(i)
−−→ −
n
P
i=1
M
σ(i)
N
2
−−−−−→
· e
σ(i)
−−→
=
n
P
i=1
³
M
σ(i)
N
1
−−−−−→
− M
σ(i)
N
2
−−−−−→´
· e
σ(i)
−−→ =
n
P
i=1
N
2
N
1
−−−→
· e
σ(i)
−−→ = N
2
N
1
−−−→
·
n
P
i=1
e
σ(i)
−−→ = const. Q.E.D.
Let us prove that the function
f
σ
= f
σ
(N ) + N N
−→
0
·
n
X
i=1
e
σ(i)
−−→ =
n
X
i=1
M
σ(i)
N
0
−−−−−→
· e
σ(i)
−−→,
where N
0
is an arbitrary fixed point in the plane, is the desired one.
Indeed, the value of f
σ
does not depend on N and increases under any rearrangement described in the
algorithm.
Thus, we have found the “quality function”, f
σ
, which only depends on the arrangement σ of the
searchlights and demonstrated how to increase its value if a point in the plane is not lighted up. Since f
ω
as the function of its index, the arrangement (for a fixed arrangement it is a constant as we just proved),
attains its maximum for an arrangement ω, the entire plane is lighted up in this case.
Extension. (Three-dimensional generalization). Let there be given a convex polyhedron with
faces Γ
1
, . . . , Γ
n
and a point O inside, as well as n arbitrary points M
1
, . . . , M
n
in space. Each face Γ
i

---

164
SOLUTIONS
defines a polyhedral angle α
i
at which this face is seen from O, see Fig. 109 f). There are n searchlights at
O, the i-th searchlight lighting up the polyhedral angle α
i
(1 < i < n); thus the entire space is lighted up
from O.
Prove that the searchlights can be moved over to points M
1
, . . . , M
n
so that the whole space will be
still lighted up. The solution of the problem almost literally repeats that of the flat version.
15. Denote: ∠ABD = α, then ∠ACD =
α
2
, ∠ADB = 90
◦
−
α
2
, see Fig. 110.
Figure 110. (Sol. A15)
From 4ABD we have
∠BAD = 180
◦
− (α + 90
◦
−
α
2
) = 90
◦
−
α
2
,
that is ∠BAD = ∠BDA and so 4ABD is an isosceles triangle: AB = BD = r.
Draw a circle centered at B with radius r. Since ∠ACD =
α
2
, point C lies on the circle (analyze this
situation on your own). Consequently, BC = r. We have AB = BC = AC, i.e., 4ABC is equilateral;
∠ABC = 60
◦
and ∠BDC = ∠BCD = 60
◦
+
α
2
. Hence, ∠ADC = (90
◦
−
α
2
) + (60
◦
+
α
2
) = 150
◦
.
16. A) Draw three mutually perpendicular planes through the center of the cube. They divide the cube
into 8 smaller cubes with edge
1
2
. Since there are 9 points, two of the points can be found in at least one of
the 8 cubes. The distance between the points does not exceed the length of the diagonal of a smaller cube,
i.e., it does not exceed
√
3
2
. Therefore, the two points are the desired ones.
B) Consider two subcases:
a) Draw three mutually perpendicular planes through the center of the cube. They divide the cube into
8 smaller cubes of edge 1. If some two of the 8 points are in one small cube, we are in the situation solved
in A) and everything is proved.
Therefore, assume that each cube has exactly one of the 8 points. Suppose now that the distance between
any two of the points is greater than 1.
Denote the distances from each of the points to the vertex of the small cube nearest to this point by
d
1
≥ d
2
≥ . . . ≥ d
8
. Choose a smaller cube such that its point A corresponds to the distance d
1
. We can
assume without loss of generality that A is within the black triangle of the upper face in the right-hand cube
nearest to us, see Fig. 111 a).
Consider its neighboring non-black cube on Fig. 111 a) and let the point B on this cube correspond to
the distance to the vertex V , which is equal to d
i
.
Draw the ball of radius d
i
centered at V and its intersections with the faces of this cube. We will produce
three quarter-circles of radius d
i
on the faces. It is on one of them that the point B lies. But then it is
easy to prove (there are many ways of doing this, see below) that the distance from A to any point of an
arbitrary quarter-circle centered at V does not exceed 1.
Here is one of such proofs. The most difficult case is the one when B is on the rear face (invisible to us) of the neighboring
cube. (Analyze the two other cases on your own.)
We introduce coordinate axes at the upper face of the front cube (the one that contains point A) and at the rear face of
the neighboring cube (the one that contains point B) as shown in Fig. 111 a). The coordinates (z, t) of A satisfy the condition
1
2
≥ z ≥ t
(1)
and the coordinates (x, y) of B satisfy the condition
x
2
+ y
2
≤ z
2
+ t
2
.
(2)

---

SOLUTIONS TO SELECTED PROBLEMS OF MOSCOW MATHEMATICAL CIRCLES
165
The squared distance between A and B is
|AB|
2
= (1 − z)
2
+ x
2
+ (t − y)
2
,
which follows from triangles 4AM B and 4M BH, since AM ⊥ M H and BH ⊥ M H. After simplification and taking (2) into
account we get:
|AB|
2
= 1 − 2z + (z
2
+ t
2
) + (x
2
+ y
2
) − 2yt ≤ 1 − 2z + 2(z
2
+ t
2
) − 2yt.
Since z
2
+ t
2
≤ 2z
2
≤ z ≤ z + yt (we have made use of (1)), we have:
−2z + 2(z
2
+ t
2
) − 2yt ≤ 2(z
2
+ t
2
− (z + yt)) ≤ 0
and, therefore, |AB|
2
< 1.
This contradiction proves the statement of the problem.
b) Let us place the cube on its vertex V so that one of its great diagonals is perpendicular to the
horizontal plane. Put a point in each of the other vertices and number them 1 to 7, as shown in Fig. 111 b).
Figure 111. (Sol. A16)
Move points 1, 2, 3 over a short distance ε along the edges 1V , 2V and 3V ; we get points 1
0
, 2
0
, 3
0
. Then
choose a number δ many times smaller than ε, e.g. 100 times smaller, and move points 4, 5, 6 to V over the
distance δ along the diagonals of the squares shown in Fig. 111 a) and denote the new points by 4
0
, 5
0
, 6
0
.
Point 7 will not be moved.
It is easy to check that the distance between any two of 7 “hatched” (see Prerequisites on Dirichlet’s
principle) points is strictly greater than 1 (verify it yourself).
17. a) If the planes are parallel, the statement of the problem is obvious and so it suffices to consider
the case when they are not parallel. Project the solid body under consideration to the intersection line l of
the given planes. We get segment AB.
On the other hand, the projection of the body to l can be obtained by projecting the body first to any
of the given planes and then by projecting the projection thus obtained to l. The result is that both circles
— projections of the body to our planes — are projected onto the segment AB whose length coincides,
therefore, with the length of the diameter of each circle. Hence, the circles are identical.
Remark. The body is not necessarily a ball: it can be of a complex shape, e.g. neither convex nor flat. This body lies in
the intersection of two identical infinite cylinders perpendicular to the planes.
b) Just as in a), we can prove that the projections of the vertices of each polygon on l, the intersection
line of the planes, are the same points A
1
, . . . , A
n
. In addition, the centers of both regular n-gons are
projected into the same point O on l (to prove this use the theorem on three perpendiculars). Denote the
radii of the circles circumscribed around the regular n-gons by R and R
0
; it is obviously sufficient to prove
that R = R
0
. So let us find the sum OA
2
1
+ . . . + OA
2
n
:
n
X
k=1
OA
2
k
=
n−1
X
k=0
h
R cos
³
α +
2πk
n
´i
2
= R
2
n−1
X
k=0
cos 2
³
α +
2πk
n
´
+ 1
2
=
nR
2
2
.

---

166
SOLUTIONS
Here we made use of the fact that
n−1
X
k=0
cos 2
³
α +
2πk
n
´
= 0;
this equality follows from the fact that the sum of vectors drawn from the center of a regular polygon to its
vertices is zero.
In the same way,
n
P
k=1
OA
2
k
=
nR
02
2
; hence, R = R
0
and the two n-gons are equal, Q.E.D.
19. Let us assume the contrary and let, for example,
√
2 = 1. . . .
|{z}
k
77 . . . 7
| {z }
5000001
. . . ,
k ≤ 4 999 998.
Then A =
r
10
k
+
7
9 × 10
k
, where r consists of the integer part and the first k digits of the decimal representation
of
√
2, approximates
√
2 with an accuracy to 10
−k−5000001
and |a
2
−2| = (a+
√
2)|A−
√
2| ≤ 3·10
−k−500001
<
10
−k−5000000
.
But on the other hand, |A
2
− 2| is a rational number with denominator (9 · 10
k
)
2
; hence, |A
2
− 2| ≥
1
(9 · 10
k
)
2
> 10
−2k−2
. Therefore, −k − 5000000 < −2k − 2 or k > 4999998. Contradiction.
20. a) If n airplanes flew to the airfield O from the airfields A
1
, . . . , A
n
, this means that in each triangle
4A
1
OA
i+1
the sides OA
i
and OA
i+1
are smaller than A
i
A
i+1
. Hence, ∠A
i
OA
i+1
> 60
◦
for any i =
1, . . . , n − 1.
But then the sum of these angles is greater than n × 60
◦
and, on the other hand, it is 360
◦
, implying
n < 6, i.e., n ≤ 5.
b) For both the spherical and the flat triangles A
i
OA
i+1
it is also true that the greater angle subtends
the longer side. Therefore the above reasoning can be applied literally to the case of the sphere. (The sum
of the angles of a spherical triangle is > 180
◦
.)
22. Obviously, cos α = ±
4
5
. Let for example, cos α =
4
5
.
Set sin kα =
a
k
5
k
, cos kα =
b
k
5
k
. Then the trigonometric formulas for the sine and cosine of the sum yield
a
k+1
= 4a
k
+ 3b
k
,
b
k+1
= −3a
k
+ 4b
k
.
This immediately implies that a
k
and b
k
are integer for all k. It remains to prove that they are not divisible
by 5. The easiest way to do this is to notice (and prove by induction) that a
k
≡ 3
k
6≡ 0 (mod 5) and
b
k
≡ 3
k−1
4 6≡ 0 (mod 5).
23. Note that if the three positions of the switch are labeled by 1, 2, 3 and the colors of the bulbs are
also labeled by 1, 2, 3 then the situation described in the problem coincides with that of Problem 30.2.10.5
(its solution is given in Part 2).
25. Multiply the equation by cos
³
3π
11
´
and express sin
³
kπ
11
´
· cos
³
3π
11
´
and cos
2
³
3π
11
´
as a sum. We
get
sin
³
3π
11
´
+ 2 sin
³
5π
11
´
− 2 sin
³
π
11
´
=
√
11 cos
³
3π
11
´
.
Squaring this equation and replacing again all products in terms of sums, and the squares in terms of
the doubled angles we get after simplification
1 + 2 cos
³
2π
11
´
+ 2 cos
³
4π
11
´
+ 2 cos
³
6π
11
´
+ 2 cos
³
8π
11
´
+ 2 cos
³
10π
11
´
= 0.
which is obviously equivalent to the initial equation.
The latter identity can be also obtained geometrically. Namely, put the center of the right 11-gon in the
origin, align the 11-gon symmetrically with respect to the x-axis and consider the projections of all vectors
from the origin into the vertices to the x-axis, see Fig. 112.
The sum of the projections is clearly equal to the left hand side of the above equation. But since the
sum of these vectors is obviously equal to ~0, so is the sum of their projections, as required.
26. Let us rewrite the given equation in the form
520(x − 1)(yzt + y + z) + 520(zt + 1) = 57(yzt + y + z)
Now, it is clear that if x > 1, then the left hand side is greater than the right hand side and there are no
solutions.

---

SOLUTIONS TO SELECTED PROBLEMS OF MOSCOW MATHEMATICAL CIRCLES
167
Figure 112. (Sol. A25)
Thus, x = 1, and the equation takes the form
57(yzt + y + z) = 520(zt + 1)
or
57z = (520 − 57y)(zt + 1).
Since 0 < z < zt + 1, we should have 57 > 520 − 57y > 0 which is only possible for y = 9. Substituting
y = 9 we get 57z = 7(zt + 1).
Applying similar trick for the third time we finally get xyzt = 1978. (The problem was suggested in
1978.)
Another solution. If you can notice that the equation can be rewritten in the form:
x +
1
y +
1
z + 1t
= 1 +
1
9 +
1
7 + 18
you immediately get
x = 1,
y = 9,
z = 7,
t = 8.
Indeed, if two numbers, e.g. continued fractions, are equal, then their integer and fractional parts are equal,
too. This implies the uniqueness of expression of a number as a finite continued fraction.
29. A) The areas of triangles OAH, OAB and OBM cannot be equal. Indeed, if we assume the
opposite and the areas of the triangles OAH, OAB and OBM are equal, see Fig. 113 a), then the fact that
S
OAB
= S
OBM
implies that OA = OM (the heights of these triangles dropped from the common vertex B
to the bases coincide) and the fact that S
OAB
= S
OAM
implies that OB = OH. Thus, BH and BM are
divided in halves at O. Hence, ABM H is a parallelogram and so BM and AH are parallel. This contradicts
the fact that they meet at C.
Consequently, if some three areas of four considered are the same and are equal to S, then one of the