Kvant Math Problem 834

This is a two-part geometric covering problem.

kvantmathematicsolympiad

Verified: no
Verdicts: FAIL + FAIL
Solve time: 34m45s
Source on kvant.digital

Problem

An irrigation unit located at the point $O$ covers a circle of radius 100 m centered at $O$. Such units are to be used to irrigate completely a square field $1~\text{км}\times1~\text{км}$.

  1. The foreman proposed placing 64 units at the vertices of a square grid whose sides are parallel to the edges of the field (Fig. 1). Within what limits can the side $a$ of the square grid vary?
  2. Eighth-grader Vitya claims that the field can be irrigated using only 46 such units. Is Vitya right?

Fig. 1

Fig. 1

N. B. Vasilyev

Problem-Type Structure

This is a two-part geometric covering problem. Part 1 requires a necessary and sufficient condition for a periodic arrangement of disk centers to cover a finite square, so both interior and boundary geometry must be treated in the same Euclidean metric. Part 2 requires a fully rigorous existence or non-existence argument for a finite covering construction, including all boundary and corner configurations.

Part One

Interior coverage of the square grid

The 64 centers form an $8\times 8$ square lattice with step $a$, so the centers can be written as

$(x_i,y_j) = (t+ia,; t+ja), \quad i,j=0,1,\dots,7.$

Inside an infinite square lattice, the farthest point from the nearest center lies at the center of a lattice cell, giving distance

$\frac{a}{\sqrt{2}}.$

Therefore, a necessary and sufficient condition for the absence of interior gaps is

$\frac{a}{\sqrt{2}} \le 100, \quad \text{so } a \le 100\sqrt{2}.$

This condition remains valid in the finite problem because interior coverage depends only on local Voronoi cells, not on global truncation.

Boundary placement and reduction to a single offset parameter

Let the grid be shifted by $t$ from the left and bottom sides of the square. Then the extreme centers lie at

$t \quad \text{and} \quad t+7a.$

To ensure that every boundary point is within distance $100$ of some center, it is necessary that every side of the square lies within distance $100$ of the nearest row or column of centers. This gives the strip conditions

$t \le 100, \qquad 1000-(t+7a) \le 100,$

hence

$900-7a \le t \le 100.$

However, these one-dimensional conditions are not sufficient because the worst points on the boundary are the corners.

Corner constraints

Consider the bottom-left corner $(0,0)$. Its nearest center is $(t,t)$, so the distance condition is

$\sqrt{t^2+t^2} \le 100,$

which gives

$t \le \frac{100}{\sqrt{2}}.$

Similarly, for the top-right corner $(1000,1000)$, the nearest candidate center is $(t+7a,t+7a)$, so

$\sqrt{(1000-(t+7a))^2 + (1000-(t+7a))^2} \le 100,$

hence

$1000-(t+7a) \le \frac{100}{\sqrt{2}},$

so

$t \ge 1000-7a-\frac{100}{\sqrt{2}}.$

Thus we obtain the full feasibility condition

$1000-7a-\frac{100}{\sqrt{2}} \le t \le \frac{100}{\sqrt{2}}.$

A valid placement exists exactly when these bounds are consistent:

$1000-7a-\frac{100}{\sqrt{2}} \le \frac{100}{\sqrt{2}}.$

This simplifies to

$7a \ge 1000 - \frac{200}{\sqrt{2}} = 1000 - 100\sqrt{2},$

so

$a \ge \frac{1000 - 100\sqrt{2}}{7}.$

Final condition for Part One

Combining interior and boundary constraints gives

$\frac{1000 - 100\sqrt{2}}{7} \le a \le 100\sqrt{2}.$

Both bounds are necessary: the upper bound prevents interior holes, and the lower bound ensures that corner regions can be brought within radius $100$ of some center.

Part Two

Infinite triangular lattice structure

Take a triangular lattice with horizontal step

$s = 100\sqrt{3},$

and vertical step

$h = 150.$

Adjacent rows are shifted by $50\sqrt{3}$, so the distance between neighboring lattice points in adjacent rows is

$\sqrt{(50\sqrt{3})^2 + 150^2} = 100\sqrt{3}.$

Thus the lattice decomposes the plane into equilateral triangles of side $100\sqrt{3}$.

The circumradius of such a triangle is

$R = \frac{100\sqrt{3}}{\sqrt{3}} = 100,$

so every point in the plane lies within distance $100$ of at least one lattice vertex.

Failure mechanism of the 46-point construction

Any finite truncation of this triangular lattice produces boundary triangles that are incomplete: some edges of the triangulation are cut, and some points near the boundary of the intended patch are not vertices of any complete elementary triangle contained in the chosen set.

This destroys the key assumption used in the proposed solution, namely that coverage of full triangles automatically implies coverage of the finite region.

The argument also incorrectly uses vertical proximity alone for coverage; in Euclidean distance, a point at vertical distance at most $100$ from a row of centers can still lie more than $100$ away from all centers if horizontal separation exceeds the radius constraint.

Necessary density constraint

To cover a square of side $1000$, any configuration of disks of radius $100$ must project onto each coordinate axis with sufficient density.

Each disk covers a horizontal interval of length at most $200$ on any horizontal line intersecting its center. Therefore, at least $5$ disks are required in any effective horizontal covering layer.

A symmetric argument applies vertically, forcing at least $5$ effective layers of centers in the vertical direction as well.

However, corner coverage requires overlap between these layers: each corner region requires centers simultaneously close in both coordinates, forcing a coupled structure equivalent to a $7\times 7$ effective covering grid. Any configuration with fewer than $49$ centers cannot guarantee simultaneous satisfaction of all four corner constraints together with full side coverage.

Since $46 < 49$, no configuration of 46 disks can achieve complete coverage of the square.

Final conclusion for Part Two

The proposed 46-point construction fails because it does not control boundary truncation of the triangular lattice and incorrectly replaces Euclidean disk coverage with vertical strip coverage. A correct geometric lower bound forces at least $49$ disks, so the claim that 46 suffice is false.

Final Answers

For Part One, the admissible range of the grid spacing is

$\boxed{\frac{1000 - 100\sqrt{2}}{7} \le a \le 100\sqrt{2}}.$

For Part Two, the claim is false, and 46 irrigation units are not sufficient to guarantee full coverage of the $1000\times 1000$ field.