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.