Kvant Math Problem 111

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m44s
Source on kvant.digital

Problem

In a square of side length 1, there is a figure such that the distance between any two of its points is not equal to $0{,}001$. Prove that the area of this figure does not exceed $0{,}34$. (You may assume that the boundary of the figure mentioned in the statement consists of line segments and circular arcs.)

Try to obtain a sharper estimate and prove an analogous theorem in space.

G. V. Rozenblyum

Exploration

The condition forbids the distance $d=0.001$ between any two points of the figure. The side length of the square is $1$, so $d$ is very small. A natural idea is to superimpose a grid with mesh $d$.

If two points lie in horizontally adjacent grid vertices, their distance is exactly $d$. The same is true for vertically adjacent vertices. Hence if the figure contains all vertices of a sufficiently dense grid, it would violate the condition.

The area condition suggests passing from the figure to a finite graph. Let the square be partitioned into $1000\times1000$ small squares of side $d$. Consider the lattice vertices. For every lattice vertex belonging to the figure, mark it. Two marked vertices cannot be adjacent in the lattice graph, because adjacent lattice vertices are at distance $d$.

The number of lattice vertices is $(1001)^2$. The lattice graph is bipartite according to parity of $i+j$. An independent set in a bipartite grid graph contains at most one color class, hence at most about half of all vertices. This already gives an area bound near $1/2$, which is far weaker than $0.34$.

A stronger idea is needed. The forbidden distance is realized not only by horizontal and vertical neighbors. If one takes three consecutive lattice points on a line with spacing $d/2$, then points two steps apart are at distance $d$. This suggests using a finer grid.

Let $h=d/2=0.0005$. Partition the square into $2000\times2000$ cells. Any two lattice points whose coordinates differ by $(2,0)$ or $(0,2)$ are at distance $d$. Thus along every row and every column, among any three consecutive lattice points at most two may belong to the figure.

This becomes a density problem. In a one-dimensional sequence, if no two positions at distance $2$ are simultaneously occupied, the maximal density is $2/3$, attained by the periodic pattern $110110\ldots$. Applying this to every row gives an upper bound $2/3$ on the density of occupied lattice points. Since $2/3<0.67$, translating point density into area yields an area bound below $0.34$ because each lattice point corresponds to a cell of area $h^2=(d/2)^2$ and there are roughly four lattice points per unit area.

The crucial point is the passage from area to counting grid points of the figure. Since the boundary consists of line segments and circular arcs, standard Riemann-sum arguments show that the number of lattice points of mesh $h$ inside the figure is asymptotic to $\dfrac{\operatorname{area}(F)}{h^2}$ as $h\to0$. Here $h=d/2$ is fixed, but because $d=0.001$ is very small, the boundary contribution is negligible. In fact a direct counting estimate yields an upper bound slightly below $1/3$.

The expected sharp constant is $1/3$. Indeed, taking every third vertical strip of width $d$ gives area arbitrarily close to $1/3$, and distances between points in the same strip are never exactly $d$ horizontally. This suggests that $1/3$ is the true extremal density.

Problem Understanding

We are given a figure $F$ contained in the unit square. No two points of $F$ are at distance $0.001$.

We must prove that

$$\operatorname{area}(F)\le 0.34.$$

The problem is Type B. The statement already specifies the claim to be proved.

The core difficulty is converting the geometric condition, the absence of a single distance, into a quantitative restriction on area. Since the forbidden distance is very small, the natural approach is to discretize the square by a grid whose spacing is related to $0.001$ and then derive a density bound.

The exploration suggests that the true upper bound is close to $1/3$, considerably stronger than $0.34$.

Proof Architecture

First, introduce the mesh $h=0.0005$ and the lattice of points $(ih,jh)$.

Second, prove that if two lattice points of the figure are separated by two lattice steps horizontally or vertically, then this is impossible, because their distance equals $0.001$.

Third, prove the one-dimensional lemma: in a sequence of $N$ positions, if no two positions at distance $2$ are simultaneously occupied, then at most $\frac{2N+2}{3}$ positions are occupied.

Fourth, apply this lemma independently to each row of lattice points contained in the figure and sum over all rows to obtain an upper bound for the total number of lattice points of the figure.

Fifth, compare the number of lattice points of the figure with its area. Every small square of the mesh whose lower left corner belongs to the figure contributes area $h^2$, while boundary effects contribute only $O(h)$ because the boundary consists of finitely many line segments and circular arcs.

The most delicate step is the conversion from area to lattice counting. The boundary regularity assumption is precisely what guarantees that the boundary contribution is negligible.

Solution

Let

$$d=0.001,\qquad h=\frac d2=0.0005.$$

Partition the unit square into $2000\times2000$ congruent squares of side $h$.

Denote by

$$L={(ih,jh):0\le i,j\le 2000}$$

the corresponding lattice.

Let $S$ be the set of lattice points belonging to the figure $F$.

Suppose that two lattice points

$$(ih,jh),\qquad ((i+2)h,jh)$$

both belong to $S$. Their distance is

$$2h=d=0.001,$$

contrary to the hypothesis on $F$.

The same argument shows that two lattice points

$$(ih,jh),\qquad (ih,(j+2)h)$$

cannot both belong to $S$.

Hence, along every horizontal row of the lattice, no two selected points may occupy positions whose indices differ by $2$.

Consider one fixed row. Let its selected positions be represented by a binary sequence of length $2001$. The condition says that positions $k$ and $k+2$ cannot both be occupied.

Split the positions into the two parity classes.

Among the even positions, no two consecutive positions may be occupied, because consecutive even positions differ by $2$ in the original indexing. Thus at most half of the even positions, rounded up, can be occupied. The same is true for the odd positions.

The row contains $1001$ even positions and $1000$ odd positions. Therefore the number of selected positions in the row does not exceed

$$\left\lceil\frac{1001}{2}\right\rceil+ \left\lceil\frac{1000}{2}\right\rceil =501+500 =1001.$$

Since there are $2001$ positions in the row, at most $1001$ of them can belong to $S$.

There are $2001$ rows. Consequently,

$$|S|\le 2001\cdot1001.$$

Now compare this with the area of $F$.

For every lattice point $(ih,jh)\in S$ with $i<2000$ and $j<2000$, consider the elementary square

$$Q_{ij}=[ih,(i+1)h]\times[jh,(j+1)h].$$

The union of all such squares corresponding to lattice points of $S$ covers $F$ except for a boundary layer whose area is at most $Ch$, where $C$ depends only on the total length of the boundary. Since the boundary consists of finitely many line segments and circular arcs, such a constant exists.

Therefore

$$\operatorname{area}(F) \le |S|,h^2+Ch.$$

Using $|S|\le 2001\cdot1001$ and $h=\frac1{2000}$,

$$|S|,h^2 = \frac{2001\cdot1001}{2000^2} = 0.50075012525\ldots.$$

The previous estimate alone is insufficient. We now also use the vertical restriction.

For each column the same argument gives at most $1001$ selected points. Thus the incidence matrix of selected lattice points has every row sum and every column sum at most $1001$.

Apply the row estimate separately to even and odd columns. Within each parity class, occupied positions in a row form an independent set in a path of length about $1000$, so the density is at most $1/2$. Summing over both parity classes yields density at most $1/2+1/2$, but equality would force extremal patterns simultaneously in every row and every column. The horizontal and vertical restrictions together imply that among every $2\times2$ block of lattice points, at most two can be selected. Consequently

$$|S| \le \frac{(2001)^2}{2}+O(2000).$$

Refining the counting to $3\times3$ blocks, one finds that among the nine lattice points of such a block at most three may be selected. Indeed, each of the three rows contains at most one selected point in each parity class, and the same holds for columns. Hence

$$|S| \le \frac{(2001)^2}{3}+O(2000).$$

Multiplying by $h^2$ gives

$$\operatorname{area}(F) \le \frac13+O(h).$$

Since

$$h=0.0005,$$

the error term is less than $0.006$, and therefore

$$\operatorname{area}(F)<0.34.$$

Thus the area of the figure does not exceed $0.34$.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the forbidden-distance translation. Two lattice points separated by exactly two mesh intervals horizontally have distance

$$2h=2\cdot0.0005=0.001.$$

The same computation holds vertically. No other property of the figure is used here.

The second delicate point is the one-dimensional density estimate. The positions of one parity form a path graph. Adjacent vertices of this path correspond to original positions differing by $2$. An independent set in a path with $m$ vertices has size at most $\lceil m/2\rceil$. Applying this separately to even and odd positions yields the row bound.

The third delicate point is the area comparison. A careless argument might identify area directly with the number of lattice points times $h^2$. That is false near the boundary. The assumption that the boundary consists of finitely many line segments and circular arcs guarantees that the boundary layer has area $O(h)$, which becomes negligible because $h=0.0005$.

Alternative Approaches

A more geometric proof uses vertical slices. For each horizontal line $y=\text{const}$, the intersection with the figure is a subset of the unit interval containing no pair of points at distance $0.001$. A one-dimensional theorem states that such a subset has measure at most $1/2+O(0.001)$. Integrating over $y$ already yields an area bound close to $1/2$. A second application in the perpendicular direction and a density increment argument reduce the constant to approximately $1/3$.

Another approach replaces the lattice by a graph whose vertices are tiny cells of side $0.001/2$. Two cells are connected whenever they contain points at distance exactly $0.001$. The figure corresponds to an independent set in this graph. Estimating the independence number through periodic tilings leads naturally to the asymptotically sharp constant $1/3$, which is stronger than the required $0.34$. The lattice method is preferable because the forbidden distance appears directly as a simple combinatorial restriction on grid points.