|
WIMBLEDON
provided by David Jordan
Wimbledon had decided to move forward into the 21st century by replanting courts with new "Astral-Turf"©**. However, it is blindingly expensive and they would like to minimize their purchase. The sod is engineered to grow very rapidly, but in a very special way. It must be purchased in 1ft x 1ft clumps, and must be laid out on a grid pattern of 1ftx1ft squares. The size of the space the Wimbledon is trying to fill is 100ft x 100ft.
Here are the rules: Any time there is an empty square (X on the sample grid) neighboring 2 or more filled squares (the O's, dummy), the empty patch will grow full by the next day. Propose a minimal plan for an initial scattering of sod so that eventually all squares will be filled. (i.e. try to plant the least number of squares, and don't worry about how many "turns" it takes to fill it all).
A correct solution will include a proposal for the initial scattering and a proof that it is a minimal (not necessarily the minimal) solution.
* As best I know, this problem (modulo my asinine story accompanying it) is due to György Elekes, Eötvös University in Budapest.
** Quiet lad, ya wanna get sued?!
|
|