Lake Covering Problem
A circular lake of radius
meters must be covered by rectangular boards of length
meters.
Rectangular boards of all widths are available, but the cost of a covering is the total width of the boards used. Clearly the lake can be covered by using parallel boards of total width
meters.
Is there a more efficient covering possible? Here are examples of two competing coverings.

Solution to Particles Riddle
In a previous post I discussed the Particles riddle, a solution of which is as follows. Cover the unit square by four closed subsquares of side length 1/2, denoted
as in the figure. Suppose that the initially awake particle is located at
, and there are sleeping particles in
(the case when some of these are unoccupied is easy to handle.) The particle at
wakes up a particle at some point
by time
. During the next
time units, one of these two particles can travel to wake a particle in some
in
, and at the same time, the other can travel to wake a particle at some
in
. In another
time unit, one of the particles from
can travel to
and one of the particles at
can travel to
. Thus by time
, there will be an awake particle in each of the originally occupied subsquares
. The argument can now be iterated in each of these subsquares. Repeated subdivision will yield a geometric series
as an upper bound for the time needed to reach all
particles. The constant 6.2 can certainly be improved; we will not try to optimize this constant. See also a similar solution posted by Sang-il Oum here.

The argument above readily generalizes to higher dimensional cubes (where the constant will depend on dimension) and to other self-similar sets. Compactness and convexity are not enough, however: Let
be an orthonormal sequence in Hilbert space. Then the closed convex hull of
is compact, but the time needed to reach the first
vertices
is of order
.
A metric space
is called a
if the distance between any two points equals the length of the shortest curve between them (In this case one also says that
is an instrinsic metric on
). In particular, a convex set in a Banach space is a length space; for the particle problem, it is natural to restrict attention to length spaces. The assumption that the particles travel at most at unit speed means that their paths are Lipschitz maps from
to
with Lipschitz constant
.
A large class of length spaces where any finite collection of points can be reached in bounded time are
length spaces. A metric space
is called
if there is some doubling constant
such that every ball
in
of any radius
, can be covered by at most
balls of radius
. See https://en.wikipedia.org/wiki/Doubling_space.
The following statement is easily proved by induction on
: Given
particles, one of them awake, in a doubling length space with doubling constant
and diameter
, all particles can be woken up by time
. (As before, awake particles travel at unit speed).