60-odd years of moscow mathematical

4ANB). This can be done by the standard method of transferring segments of size AM , AB and M B with the help of a
compass to the plane (of the paper). The circle circumscribed around 4AM B is the required one.
2) It is easy to draw this circle also on the ball itself, not just on the plane, if the legs of the compass can bend.
35. Let us numerate parts of both partitions 1 to 100: A
1
, . . . , A
100
and B
1
, . . . , B
100
. Let S
ij
be the
area of A
i
∩ B
j
. Make an array of size 100 × 100, where the (i, j)-th number is S
ij
. Since the parts A
i
and
B
j
of the partitions are of the same area, we have:
n
X
i=1
S
ij
=
n
X
j=1
S
ij
=
1
100
.
Define a “snake” to be a set of 100 numbers S
ij
in distinct rows and distinct columns. If all numbers S
ij
constituting the “snake” are nonzero, the required 100 points should be placed in the respective intersections
A
i
∩ B
j
. Thus, it remains to prove the existence of a snake built of nonzero numbers; such a snake is briefly
called a nonzero snake.
Observe (it is quite obvious) that for any k rows selected there are k columns in whose intersection
points with the rows selected there are at least k nonzero numbers S
ij
.
Indeed, if the sets A
i
1
, . . . , A
i
k
have a nonempty intersection with l elements B
j
1
, . . . , B
j
l
of the second
system, then A
i
1
∪ . . . ∪ A
j
k
⊂ B
j
1
∪ . . . ∪ B
j
l
. Hence, k ≤ l. Contradiction.
Let us prove the existence of a nonzero snake by induction on size of a minor
1
. Namely, let us prove
that for any k × k minor with a nonzero snake and an arbitrary (k + 1)-th row there exists the (k + 1)-st
column such that the (k + 1) × (k + 1) minor thus obtained also has a nonzero snake.
1
A k × k minor is a set of k
2
squares — the table formed by the points of intersection of k rows and k columns.

---

SOLUTIONS TO SELECTED PROBLEMS OF MOSCOW MATHEMATICAL CIRCLES
171
The base of the induction: Take any nonzero element (a 1 × 1 minor) and add any nonzero element from
another row. Adding also two more elements which are in the same rows and columns we get a 2 × 2 minor
with a nonzero snake.
The inductive step: Let the statement be true for all k × k minors. We can assume without loss of
generality that this minor is in the top left-hand corner of the array. Add another row. Without loss of
generality, let it be the (k + 1)-st row. We will prove that it is possible to select a column such that the
respective minor contains a nonzero snake.
By observation above, in one of the first k + 1 rows there exists a nonzero element A
il
standing to the
right of the minor, i.e., i ≤ k + 1, l > k. If A
il
stands in the (k + 1)-st row, let just augment the minor with
the l-th column and mark the element A