60-odd years of moscow mathematical

< r
2
} play the role of open intervals in the above
definition. In space the discs are replaced with open balls {x, y, z | (x − a)
2
+ (y − b)
2
+ (z − c)
2
< r
2
}.
Observe that an open interval considered not on the line but on the plane or in space does not consist
anymore of inner points: the open sets have changed.
The end of the proof is sometimes marked with a
or Q.E.D.

---

Selected lectures of mathmathematics circles
Dirichlet’s principle
(Summary of Acad. I. M. Gelfand’s lecture for 9-th –11-th graders)
First, Gelfand proposed the following
Problem: An infinite number of narrow parallel ditches
√
2 apart have been dug out across a very long
straight road, see Fig. L1. Prove that no matter how narrow these ditches are, a pedestrian with a step of
length 1 m inevitably steps into a ditch.
Figure 1. (Fig.L1)
Figure 2. (Fig.L2)
A short proof follows from Dirichlet’s or pigeonhole principle.
Indeed, suppose we can ‘wind’ the road onto a reel of circumference
√
2 m, see Fig. L2. Then all ditches
coincide and every step of the pedestrian is marked on the circle by an arc 1 m long. Let us mark the
pedestrian’s traces (points where the pedestrian touched the ground) after each step. We must prove that
at least one of these traces belongs to the interior of a small arc on the circle representing the ditches no
matter how short length h of this arc may be.
It is easy to see that if it is possible to find k and l such that the distance between the traces of the
k-th step and (k + l)-th step along the circle is less than h, then the desired statement will be easy to prove.
Figure 3. (Fig.L3)
Indeed, after l more steps the (k + 2l)-th trace moves again by a distance less than h, see Fig. L3;
next we consider another l steps, and so on. Now, it is clear that after several groups of l steps we will
inevitably discover a trace that falls in a ditch (since by hopping each time the same distance less than h
it is impossible to hop over a ditch of width h).
Thus, we should find two traces on the circle with the distance between them less than h. This is where
the rabbits (pigeons) come in handy.
Let us divide the circle into arcs of lengths less than h and call these arcs hutches. Suppose there are p
of them. If we take more than p traces (observe that no two traces coincide since
√
2 is irrational) then by
17

---

18
SELECTED LECTURES OF MATHMATHEMATICS CIRCLES
Dirichlet’s principle at least one of the hutches contains more than one trace (rabbit). The distance between
two traces that belong to one arc (hutch) is less than h. This proves our statement.
As a second example of the same realm of ideas, consider the following
Problem. Prove that there exists a power of 2 whose decimal expression begins with three nines, i.e.,
2
n
= 999 . . . .
In other words, prove that there exist integers n and k such that
999 · 10
k
≤ 2
n
< 10
k+3
or, equivalently,
k + lg(999) ≤ n lg 2 < k + 3.
It is easy to see that this problem is quite similar to the initial one, the only difference being that here
the length of the ‘step’ is equal to lg 2 and that the distance between two neighboring ‘ditches’ of width
3 − lg(999) is equal to 1.
In general, if p is not a power of 10, then among the numbers p, p
2