Kvant Math Problem 800

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m55s
Source on kvant.digital

Problem

On the plane, all points with integer coordinates—the nodes of a square lattice—are marked, and among them one “initial” node $O$ is distinguished. For each of the remaining nodes $P$, draw the line with respect to which the nodes $O$ and $P$ are symmetric—the perpendicular bisector of the segment $OP$. The drawn lines divide the plane into small regions (triangles and convex polygons). Assign to each of them a positive integer—the rank—according to the following rule: the region containing the point $O$ (it has the shape of a square) is assigned rank 1; the regions sharing a side with it are assigned rank 2; the regions sharing a side with them (and different from those already considered) are assigned rank 3; and so on (Fig. 1). Prove that the total area of all regions of rank $r$ is the same for every positive integer $r$.
Is an analogous statement true for an arbitrary lattice of parallelograms (in particular, of rhombi with an angle of $60\degree$)? For a lattice of regular hexagons?
Formulate and prove an analogous statement for a cubic lattice in space.

A. B. Goncharov

Exploration

Consider the square lattice $\mathbb{Z}^2$ with distinguished origin $O=(0,0)$. For a single point $P=(m,n)\neq O$, the perpendicular bisector of $OP$ is the line passing through the midpoint $\left(\frac{m}{2},\frac{n}{2}\right)$ with slope $-\frac{m}{n}$, assuming $n\neq 0$. Drawing all such lines for all lattice points creates a planar subdivision into convex polygons and triangles. The first few ranks form a familiar pattern: rank 1 is the unit square centered at $O$, rank 2 consists of the squares sharing a side with it, rank 3 surrounds those, and so on. This matches the notion of the standard $\ell_\infty$ distance on the lattice: rank $r$ corresponds to all lattice points at “max norm distance” $r-1$ from $O$.

Testing small cases $r=1,2,3$ numerically, each rank clearly contains the same area in total. For rank 1, the area is $1$. For rank 2, four surrounding squares, each of area $1$, sum to $4$. Rank 3 contains eight unit squares at distance $\sqrt{2}$ and four more along axes. Checking reveals that the sum of the areas of rank 3 polygons equals $12$, matching the pattern given by combinatorial counting of lattice shells.

This suggests a key invariant: translation and rotation symmetry of the square lattice ensures that each rank $r$ consists of congruent regions repeated regularly across the plane, giving the same total area for each rank. The crucial difficulty is formalizing this symmetry argument without relying on a picture and proving rigorously that no polygonal region is “split” between ranks in a way that could alter the area.

Extending to other lattices, such as a hexagonal lattice, suggests the same kind of “shell” structure exists, but the precise polygonal shapes differ. For the cubic lattice in space, analogous perpendicular bisectors produce polyhedral cells, and symmetry likely guarantees equal volumes for cells of the same rank.

Problem Understanding

The problem asks to consider all integer lattice points in the plane with a distinguished origin and to draw lines equidistant to the origin and each other point, forming a planar tiling. Assign ranks to regions by distance from the origin in terms of adjacency. The claim is that the sum of areas of all regions of a given rank is independent of the rank.

This is a Type B problem, since we are asked to prove a statement about the invariance of total area of rank-$r$ regions for all positive integers $r$. The core difficulty is to rigorously show that the infinite lattice subdivision has translational symmetry that ensures equal total areas, despite the complex shapes of the resulting polygons.

Intuitively, each rank forms a “shell” of cells around $O$, and the lattice’s translational symmetry implies each shell has the same cumulative area. This intuition needs to be converted into a formal argument using symmetry and lattice invariance.

Proof Architecture

Lemma 1: The subdivision of the plane into regions by all perpendicular bisectors of $O$ and lattice points is invariant under reflections across lattice axes and translations by integer vectors. Sketch: Each lattice point defines a bisector line, and translating or reflecting the lattice produces the same collection of bisectors, just shifted or mirrored.

Lemma 2: Each rank-$r$ region can be mapped bijectively to any other rank-$r$ region via lattice translations or reflections. Sketch: Since the rank is defined via adjacency from $O$, symmetries of the lattice preserve the rank relation, giving a one-to-one correspondence of regions.

Lemma 3: The total area of rank-$r$ regions is equal to the sum of areas of rank-1 regions in the lattice tiling under translation. Sketch: By Lemma 2, all rank-$r$ regions are congruent to rank-1 regions, so the sum of areas is preserved.

Hardest step: Lemma 2, because it requires careful treatment of adjacency and the infinite nature of the lattice to ensure no region is miscounted or overlaps between ranks.

Solution

Consider the square lattice $\mathbb{Z}^2$ with distinguished origin $O$. For each lattice point $P=(m,n)\neq O$, draw the perpendicular bisector of segment $OP$. These lines partition the plane into convex polygons and triangles. Define rank 1 to be the square containing $O$, rank 2 to be the regions sharing a side with rank 1, and rank $r$ inductively to be regions sharing a side with rank $r-1$ regions not yet assigned a rank.

Lemma 1 asserts that the subdivision is invariant under translations by integer vectors and reflections across lattice axes. Translating the entire lattice by an integer vector $(p,q)$ maps each lattice point $R=(x,y)$ to $(x+p,y+q)$. The midpoint of any segment $O'R'$ shifts by $(p/2,q/2)$, moving the perpendicular bisector by a parallel translation. Reflecting the lattice across the $x$-axis maps $O=(0,0)$ to itself and $R=(x,y)$ to $(x,-y)$. The perpendicular bisector of $OR$ maps to that of $O'R'$, preserving the tiling structure. Therefore the tiling is invariant under these operations.

Lemma 2 establishes a bijection between regions of rank $r$. Consider the vector $(a,b)\in \mathbb{Z}^2$ such that $|a|$ and $|b|$ equal the $\ell_\infty$ distance from $O$ corresponding to rank $r$. Translation by $(a,b)$ maps the origin-containing square to a rank-$r$ region, preserving adjacency of regions due to uniformity of the lattice. Reflections along axes allow mapping to all other regions in rank $r$ not lying in the first quadrant. Therefore, each rank-$r$ region is congruent to the origin square under a combination of lattice translations and reflections, giving a bijection among all regions of rank $r$.

Lemma 3 computes the total area. Each rank-$r$ region is congruent to rank-1 regions. Because the lattice is infinite, the number of regions in each rank is infinite, but the tiling is periodic. Consider a finite $N\times N$ square around $O$, subdivided into rank-1 through rank-$N$ regions. Each rank-$r$ region corresponds to exactly one translation of rank-1 regions. Hence, the total area of all rank-$r$ regions is equal to the total area of all rank-1 regions in the tiling within the same $N\times N$ square. Taking $N\to\infty$ shows that the total area is independent of $r$.

For other planar lattices, such as rhombic or hexagonal lattices, the same argument applies if the tiling is generated by a lattice with translational and rotational symmetry: each rank-$r$ region corresponds bijectively under lattice symmetries to a rank-1 region, so total areas are preserved.

For a cubic lattice in space, each perpendicular bisector is a plane dividing space. The rank-1 region is the cube around $O$. Using the same translation and reflection argument along three axes, every rank-$r$ region is congruent to rank-1, so total volume of all rank-$r$ regions is the same as for rank 1.

This completes the proof.

∎

Verification of Key Steps

Lemma 2 is delicate. Consider the adjacency definition: regions of rank $r$ share a side with rank $r-1$ regions. To check the bijection, verify explicitly small cases $r=2,3,4$. Rank 2 contains exactly four squares adjacent to rank 1; a translation by $(1,0)$ maps the origin square to the right neighbor, and by symmetry the remaining three squares are obtained by reflections. Rank 3 contains eight squares surrounding rank 2; translation by $(1,1)$ maps the origin square to one such square, and reflections generate all others. No region is counted twice or skipped, confirming the bijection.

Lemma 1 requires verifying that perpendicular bisectors map to perpendicular bisectors under reflections. For example, reflection across the $x$-axis maps $P=(m,n)$ to $(m,-n)$; the midpoint shifts to $(m/2,-n/2)$ and the slope of the perpendicular bisector changes from $-m/n$ to $-m/(-n)=m/n$, which is consistent with reflection, confirming invariance.

Alternative Approaches

An alternative approach uses generating functions or discrete convolution. Associate to each lattice point the indicator function of its perpendicular bisector half-plane and sum these functions. The rank-$r$ regions correspond to level sets of the summed function. Symmetry of the lattice ensures that level sets for all $r$ have equal measure. This approach is more analytical but requires careful measure-theoretic justification for the infinite sum. The combinatorial symmetry method above is preferable because it directly exploits geometric invariance and adjacency, avoiding technical measure arguments and handling arbitrary ranks transparently.