carpeting suppose that $S$ is a figure in the plane such that it's border doesn't contain any lattice points. suppose that $x,y$ are two lattice points with the distance $1$ (we call a point lattice point if it's coordinates are integers). suppose that we can cover the plane with copies of $S$ such that $x,y$ always go on lattice points ( you can rotate or reverse copies of $S$). prove that the area of $S$ is equal to lattice points inside it. time allowed for this question was 1 hour.
Problem
Source:
Tags: analytic geometry, rotation, geometry, combinatorics proposed, combinatorics, covering
19.08.2010 03:58
Firstly, S obviously contains a lattice point, or no lattice point in the plane could get covered. So, let $x$ be the "density" of S, or its area divided by the number of lattice points it contains. We want to prove $x = 1$. Let $d$ be a fixed integer larger than the distance between any two points of S. Cover the plane as specified in the problem, then pick a $t \times t$ square of lattice points, and let $T$ be the set of all copies of S that contain at least one of these lattice points. $T$ is contained in a $(t+2d) \times (t+2d)$ square centered at the original square of lattice points, because no shape containing a lattice point inside the square could contain a point $d$ units away. Therefore, its area is less than $(t+2d)^2$. On the other hand, each lattice point in the $t \times t$ square is covered, so $T$'s area is at least $xt^2$. Therefore, $(t+2d)^2 > xt^2 \Rightarrow 1 + 4d/t + 4d^2/t^2 > x$. Since $d$ is fixed, we can make $4d/t + 4d^2/t^2$ as small a positive number as we please by adjusting $t$, so that $1 \geq x$. Now for the other side: $T$ must contain the square $(t-2d) \times (t-2d)$ centered again at the same space, because since it covers the plane, any piece containing part of that square would have to contain a lattice point less than $d$ units away. On the other hand, the number of lattice points $T$ contains is certainly less than $(t+2d)^2$. Therefore $x(t+2d)^2 \geq (t-2d)^2$. Rearrange as $x \geq 1 - \frac{8td}{(t+2d)^2}$. The denominator is of degree 2, so $\frac{8td}{(t+2d)^2}$ can be made arbitrarily small a positive number by adjusting $t$, and $x \geq 1$. Therefore $x = 1$.
02.11.2019 19:12