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.