60-odd years of moscow mathematical

k+1,l
in it. We get a “nonzero snake” of size (k + 1) × (k + 1), see
Fig. 116 a).
Figure 116. (Sol. A35)
If i ≤ k, then the i-th row contains a marked element, A
ij
with j ≤ k. Let us delete from the minor
the i-th row and the j-th column. We get a (k − 1) × (k − 1) minor with a marked nonzero snake. By the
inductive hypothesis it can be augmented with the (k + 1)-st row and a column to a k × k minor with a
nonzero snake. Let us augment the minor again with the i-th row and the j-th column (with the element
A
ij
6= 0 marked); if the j-th column is already added, let us augment the minor with the l-th column and
mark A
il
6= 0. We get a (k + 1) × (k + 1) minor with a marked nonzero snake.
38. For example, one die is placed so that along its lateral sides stand 2, 3, 5, and 4, the other 39 dice
being placed so that along there lateral sides stand 1, 2, 6, and 5. Denote the number of 1’s, 2’s, 6’s, and
5’s over the 2 of the first die by x, y, z, t, respectively. Let us try to find a position for which the sums of
dots on the lateral sides were equal:
2 + 1 · x + 2 · y + 6 · z + 5 · t = 3 + 2 · x + 6 · y + 5 · z + 1 · t = 5 + 6 · x + 5 · y + 1 · z + 2 · t.
The first and second equalities yield, respectively:
(x − z) + 4(y − t) + 1 = 0,
4(x − z) − (y − t) + 2 = 0,
therefrom we can determine x − z and y − t and see that they are not integer.

---

172
SOLUTIONS
40. Let
a
k
= k +
1
(k + 1) + . . . +
1
n − 1
and
b
k
= k +
1
(k + 1) + . . . +
1
(n − 1) + 1
n
be the “tails” of the given continued fraction beginning with the integer k and h
k
= |a
k
− b
k
|. Then
a
k−1
− b
k−1
=
1
a
k
−
1
b
k
=
b
k
− a
k
a
k
b
k
,
k = 2, . . . , n − 1,
so h
k−1
=
h
k
a
k
b
k
<
h
k
k
2
(because a
k
> k and b
k
> k) and h
n−1
=
1
n
. Hence, the difference we are interested
in is estimated as follows:
h
1
<
h
2
2
2
<
h
3
2
2
3
2
< . . . <
h
n−1
2
2
3
2
. . . (n − 1)
2
=
1
(n − 1)!n!
,
Q.E.D.
41. Let points A, B, C move along the circles centered at O
1
, O
2
, O
3
in the same direction at an angular
speed ω; let A(t), B(t), C(t) be their positions at the moment of time t. We assume that the plane under
consideration is a complex line and O is the origin. Then the centers of the circles are complex numbers c
1
,
c
2
, c
3
, the original points are numbers z
1
, z
2
, z
3
, and the points A(t), B(t), C(t) are numbers:
A(t) = c
1
+ (z
1
− c
1
)e
iωt
;
B(t) = c
2
+ (z
2
− c
2
)e
iωt
;
C(t) = c
3
+ (z
3
− c
3
)e
iωt
.
The radii of the circles are |z
1
− c
1
|, |z
2
− c
2
| and |z
3
− c
3
|, respectively.
The center of mass of 4A(t)B(t)C(t) is the complex number
Z(t) = 13(A(t) + B(t) + C(t)) =
1
3 (c
1
+ c
2
+ c
3
) +
³
1
3 (z
1
+ z
2
+ z
3
) − 13(c
1
+ c
2
+ c
3
)
´
e
iωt
.
Consequently, the center of mass of 4A(t)B(t)C(t) is moving at an angular speed ω in the same direction
as the original points A, B, C over the circle centered at the point
1
3
(c
1
+ c
2
+ c
3
) and with radius
1
3
|(z
1
+
z
2
+ z
3
) − (c
1
+ c
2
+ c
3
)|. The center of this circle is the center of mass of 4O
1
O
2
O
3
and its radius R is the
length of the segment connecting the centers of mass of 4ABC and 4O
1
O
2
O
3
.
43. It is easy to see from Fig. 117 that β =
˘
AnB
2
, γ =
˘
BmA
2
, therefrom β +γ =
1
2
(
˘
AnB +
˘
BmA) =
360
◦
2
= 180
◦
, γ = 180
◦
− β. Hence, sin γ = sin β.
Figure 117. (Sol. A43)
By the law of sines, for 4AM C we have
CA
sin α
=
CM
sin β
=⇒
CA
CM
=
sin α
sin β
and for 4BM D
DB
sin α
=
DM
sin γ
=⇒
DB
DM
=
sin α
sin γ
=
sin α
sin β
.
Hence, CA
CM =
DB
DM , Q.E.D.

---

SOLUTIONS TO SELECTED PROBLEMS OF MOSCOW MATHEMATICAL CIRCLES
173
44. Obviously, we can assume that not all given numbers are divisible by p. On the other hand, among
the given numbers there are two, a and b, that yield the same remainder when divided by p, i.e., a − b = lp.
Suppose that a and b are not divisible by p. Clearly, d = (a, b), their GCD, is also the GCD of a and
a − b. Then
a
d
>
a − b
d
= p
l
d
≥ p, as required.
Analyze on your own the case when a and b are divisible by p.
45. Denote the function
k
P
n=1
a
n
cos nx by P (x). We see that P (x) ≥ −1 for all x under the condition of
the problem.
Let us prove that
k
P
l=0
P (
2πl
k + 1
) = 0. For this it suffices to prove that
k
P
l=0
a
1
cos
³
2πl
k + 1
´
= 0,
k
P
l=0
a
2
cos 2
³
2πl
k + 1
´
= 0,
. . . . . . . . . . . . . . . . . . .
k
P
l=0
a
k
cos k
³
2πl
k + 1
´
= 0.
But each of these sums is the sum of the real parts of complex numbers lying at the vertices of a regular
polygon, i.e., it is actually equal to 0 and the required equality is proved.
It follows, therefore, that
P (0) = −
k
X
l=1
P
³
2πl
k + 1
´
and since P
³
2πl
k + 1
´
≥ −1 for all l = 1, . . . , k, we have
P (0) ≤ −
k
X
l=1
(−1) = k.
46. Clearly, the first prompt of Guesser is arbitrary. It divides 16 possible numbers into groups 1 + 4 +
6 + 4 + 1 (if the prompt is: “11 111”, then the i-th group has numbers with i-many 1’s).
If we are unlucky as Guesser and got in the middle group we will be unable to guess.
Indeed, at the second prompt only the number of 1’s is important, not their order; 10 001 divides 6
numbers into groups 3 + 3 and 10 011 divides 6 numbers into groups 1 + 4 + 1. Therefore, it is clear that the
third prompt can not divide a group of 4 (since no prompt divides into four groups; if we do not prompt a
number of type 10 011, we will be even unable to divide the group of 3).
Remark. One can interpret the problem differently: since there stands a “five-digit number” in the
formulation, we may think that it is assumed that the first number is necessarily a 1.
49. The simplest way to solve this problem is to regard the white plane as a complex line, and consider
the locations of the man and the cat as complex numbers z
m
= z
m
(t) and z
c
= z
c
(t), respectively, that
depend on time t (t is a real number). Assume that the cat is at point O at the moment t = 0.
The cat encircles the man in three stages.
Stage 1. Denote: w =
z
c
z
m
(observe that z
m
6= 0: the man will not go to the origin because the cat
already was there). At the first stage, the cat runs along a straight line until the absolute value of w becomes
|w| = 1 +
ε
2
, where ε = λ − 1 > 0.
Stage 2. The cat moves in a special manner: so that |w| = 1 +
ε
2
at all times. At the beginning of the
second stage, arg z
c
= 0, 0 < arg z
m
< 2π, arg w = − arg z
m
< 0; all the angles (arg’s) depend continuously
on t. If the cat wanted to make w = const, it would suffice for it to move at a speed of 1 +
ε
2
. Therefore,
it has an excess of speed
ε
2
which it can use to change the argument of w. The cat runs over a distance
not greater than t(1 + ε) over the time interval t, so |z
c
| ≤ t(1 + ε) and the cat can ensure that the rate of
variation of arg w is at least
ε
2
|z|
≥
ε
2
t(1 + ε)

---

174
SOLUTIONS
Since
∞
R
c
dt
t
= ∞, the variation of arg w can be infinitely large. At stage 2, therefore, the cat increases
arg w at the maximum possible rate. The second stage terminates when arg w becomes positive.
Stage 3. Finally, the cat moves so that |z
c
| does not increase, |w| ≤ 1 +
ε
2
and arg z
c
increases at a rate
limited from below by a constant. But the man cannot run away and the path of the cat closes after a finite
time.
50. Consider one of the given points and all annuli in which it is contained. The centers of these
annuli constitute an annulus with the inner radius 2 and the outer one 3. The area of this annulus equals
9π − 4π = 5π.
Let us construct 650 of such annuli for each given point; all of them are contained in the disc of
radius 19. Suppose that the statement of the problem is false. Then no point of the plane is contained
simultaneously in 10 of the annuli constructed. Therefore, the area of the union of the annuli is greater than
650 · 5 ·
π
9
= π · 361.11...
But this is greater than the area of the disc of radius 19 in which, as we have already shown, all of the
annuli are contained. Contradiction.

---

SOLUTIONS TO SELECTED PROBLEMS OF MOSCOW MATHEMATICAL CIRCLES
175
51. Let us prove by induction that for any number x and an integer n there exists ε > 0 such that no
number from the segment ]x − ε, x[ can be represented as the sum of n numbers, each inverse to a positive
integer.
The base of induction, n = 0 is obvious: take ε = x. The inductive step: Let the statement be true for
an n; let us prove that it holds for n + 1.
For every integer q ≤ 2
n + 1
x
there exists by the inductive hypothesis a number ε
q
such that no number
from the segment ]x − ε
q
−
1
q
, x −
1
q
[ can be represented as the sum
1
a
1
+ · · · +
1
a
n
for positive integers a
i
,
i = 1, 2, ..., n. Hence, no number from the segment ]x − ε
q
, x[ can be represented as
1
a
1
+ · · · +
1
a