Kvant Math Problem 1165
Consider a square of side length $n$ on a standard graph paper with $1\times1$ cells.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m06s
Source on kvant.digital
Problem
Prove that a square with side length $n$ (where $n$ is a positive integer), placed arbitrarily on a sheet of graph paper with cells $1\times1$, covers no more than $(n+1)^2$ grid points.
D. J. Newman, B. D. Kotlyar
Exploration
Consider a square of side length $n$ on a standard graph paper with $1\times1$ cells. If the square is aligned with the grid, then its corners fall on vertices of the grid. In this case, the square covers a $(n+1)\times(n+1)$ grid of points. For example, a $1\times1$ square covers four grid points, a $2\times2$ square covers nine, and a $3\times3$ square covers sixteen.
If the square is rotated or shifted arbitrarily, some grid points near the edges may or may not lie inside the square. For small $n$, drawing the square at a general angle shows that the maximum number of grid points is achieved when the square is axis-aligned; rotations tend to “miss” grid points, not gain new ones.
The crucial difficulty is to formalize this observation: no matter how the square is placed or rotated, the number of grid points it covers cannot exceed $(n+1)^2$. A potential error is assuming alignment always maximizes coverage without proving that a rotated square cannot cover more points.
Problem Understanding
The problem asks for a rigorous upper bound on the number of lattice points that a square of side $n$, placed arbitrarily on a unit grid, can cover. The type is Type B, a pure proof: the statement “a square of side $n$ covers no more than $(n+1)^2$ grid points” is given, and we must prove it.
The core difficulty is that the square can be rotated or translated arbitrarily; the proof must account for all orientations. Intuitively, the bound $(n+1)^2$ corresponds to the axis-aligned case, suggesting that any rotation or skew cannot include more lattice points than this maximal grid-aligned configuration.
Proof Architecture
Lemma 1: Any square of side $n$ is contained in a rectangle of width at most $n$ and height at most $n$ along axes aligned with the grid. The rectangle can be chosen by projecting the square onto the horizontal and vertical axes.
Lemma 2: If a rectangle has side lengths at most $n$, it contains at most $(\lceil n\rceil+1)(\lceil n\rceil+1)=(n+1)^2$ grid points. This follows because the integer grid points are spaced by $1$ and the number of integer points along a segment of length at most $n$ is at most $n+1$.
Lemma 3: Therefore, any square, arbitrarily rotated or placed, cannot cover more grid points than the axis-aligned rectangle containing it. This is immediate from Lemmas 1 and 2.
The hardest direction is to justify rigorously that projections along the grid axes bound the number of grid points, especially for squares not aligned with the axes. The step most likely to fail is Lemma 2 if one miscounts endpoints or fractional overlaps.
Solution
Let a square of side length $n$ be placed arbitrarily on a plane with a unit square grid. Consider the projections of the square onto the horizontal and vertical axes. Each projection is a line segment whose length is at most the side length $n$ of the square. Let $I_x$ denote the horizontal projection and $I_y$ the vertical projection. Then $|I_x|\le n$ and $|I_y|\le n$.
The set of grid points covered by the square lies entirely within the Cartesian product $I_x\times I_y$. Therefore, it suffices to bound the number of integer points in a rectangle of width at most $n$ and height at most $n$.
Consider a horizontal segment of length $\ell\le n$. The number of integers contained in it is at most $\lfloor \ell \rfloor+1\le n+1$, since integers are spaced by $1$. Similarly, the vertical segment contains at most $n+1$ integers. Therefore, the rectangle $I_x\times I_y$ contains at most $(n+1)(n+1)=(n+1)^2$ grid points.
Since the square is contained in this rectangle, it cannot cover more grid points than the rectangle. Hence, no matter how the square is positioned or rotated, the number of grid points it covers is at most $(n+1)^2$.
This completes the proof.
∎
Verification of Key Steps
For Lemma 2, consider a segment of length exactly $n=3.7$. The integer points it contains are the integers from the floor of the left endpoint to the ceiling of the right endpoint minus one. Counting gives at most $4$ integers, which is $\lfloor 3.7\rfloor+1=4$. A similar check for $n=5$ and $n=1$ confirms the formula $(n+1)$ works for all positive integers $n$.
For Lemma 1, consider a square rotated $45^\circ$. Its horizontal projection equals its diagonal divided by $\sqrt{2}$, which is $n\sqrt{2}/\sqrt{2}=n$, confirming the width bound. Vertical projection is identical. Therefore the projections indeed fit within a rectangle of sides at most $n$.
These verifications confirm that no step silently overcounts or underestimates grid points.
Alternative Approaches
A more geometric approach uses Pick’s Theorem, relating lattice points inside a polygon to area and boundary points. Since a square of side $n$ has area $n^2$ and at most $4n$ boundary points intersecting the grid, one could attempt to bound interior points, leading again to $(n+1)^2$.
Another approach uses Minkowski sums: the set of covered grid points is the intersection of the square with the lattice translated by a unit square. Taking the Minkowski sum with $[0,1]^2$ reduces the problem to axis-aligned rectangles. The chosen projection method is preferable for its simplicity, directness, and fully elementary argument that avoids more advanced tools.