22
$\begingroup$

For $C=1$, it has been proved here that every shape in the plane having area less than $1$ can be translated and rotated so that it does not touch any element of $\mathbb Z^2$. (In fact, for $C=1$, only translation is necessary.)

What is the largest $C$ for which this is true?

I think the answer is $\frac{\pi}{2}$. This is an upper bound on the answer as a disk of area $\frac{\pi}{2}$ cannot avoid $\mathbb Z^2$. But I don't know how to prove that the largest $C$ is exactly $\frac{\pi}{2}$.

$\endgroup$
  • $\begingroup$ related: math.stackexchange.com/questions/1290823/… $\endgroup$ – Henry May 22 '15 at 10:03
  • $\begingroup$ @Henry It's my question asked in a few days ago.But nobody given the suitable answer. $\endgroup$ – lanse2pty May 22 '15 at 10:06
  • $\begingroup$ You might be interested in the Minkowski convex body theorem. $\endgroup$ – Cameron Williams May 22 '15 at 14:52
  • $\begingroup$ Could you define shape please. Does is at to be convex? Connected? Closed? $\endgroup$ – Gilles Bonnet May 30 '15 at 14:12
  • 1
    $\begingroup$ Perhaps a Reuleaux triangle would work. It minimises the area for a shape of constant width and one with a width of $\sqrt 2$ has smaller area than the other lower bounds $\endgroup$ – Dan Robertson May 30 '15 at 18:15
9
+200
$\begingroup$

It turns out a $1\times\sqrt{2}$ rectangle works, giving us $$C\le\sqrt{2}\approx1.414$$

our winner

EDIT: Please see Christian Blatter's proof (currently at the bottom of this page) that this region works. It is much more straightforward than mine. The following is the proof I originally gave:

Proof:

Definition: The associated disk to an instance of this rectangle in the plane shall be the disk of radius $r=\frac{1}{\sqrt{2}}$ centered at the same center as the rectangle. The boundary of the associated disk is shown in black in the following figure.

associated disk

Lemma: Every closed disk of radius $\frac{1}{\sqrt{2}}$ in the plane contains an integer point.

Proof of Lemma: Let the center of the disk be $\left(c_1,c_2\right)$. Then the disk contains at least one of the integer points $\left(\lfloor c_1\rfloor,\lfloor c_2\rfloor\right)$,$\left(\lfloor c_1\rfloor,\lceil c_2\rceil\right)$,$\left(\lceil c_1\rceil,\lfloor c_2\rfloor\right)$ or $\left(\lceil c_1\rceil,\lceil c_2\rceil\right)$, since the boundary of the disk circumscribes a unit square.

Main Lemma: If the associated disk to an instance of the rectangle contains an integer point $P$, then the rectangle also contains an integer point.

Proof of Main Lemma:

Case $1$ (trivial): $P$ lies in the intersection of the rectangle and the disk, so the rectangle contains an integer point.

Case $2$: $P$ lies outside the rectangle (see figure below). We claim at least one of $P+(1,0)$, $P+(0,1)$, $P-(1,0)$, or $P-(0,1)$ lies within the rectangle. Notice that any arc of length at least $\frac{\pi}{2}$ on the circle of radius $1$ centered at $P$ contains at least $1$ of these points.

the arc

Claim for Case $2$: Such an arc is completely contained in the rectangle for every point $P$ outside the rectangle and inside the associated disk, so the rectangle contains an integer point.

Proof of Claim for Case $2$: It suffices to check such $\frac{\pi}{2}$ arcs exist just on the arc segment between the rectangle and circle intersections, because we can shift the arc for any $P$ on this boundary up to the line segment (up as defined in the following picture) while maintaining at least that arc length. This however is easy to show because the circle of radius $1$ around any $P$ on the boundary of the disk intersects the boundary of the disk at the diametrically opposed points, so the corresponding angle (and therefore arc length) is $\frac{\pi}{2}$.

arc argument

up

At long last we can conclude $$C\le\sqrt{2}$$

Note this approach lends itself to further improvement (in particular we don't need the full rectangle to get arcs of length $\frac{\pi}{2}$).

$\endgroup$
10
$\begingroup$

This seems to be a difficult problem. In the following I propose a shape that has area strictly $<{\pi\over2}$ and cannot be placed on the integer lattice without hitting a lattice point.

enter image description here

In the figure the lattice is turned by $45^\circ$, whence $r={1\over\sqrt{2}}$. The offset $x$ is a small parameter. One computes $$a^2=r^2+x^2, \quad b^2=a^2-(r-x)^2 =2rx, \quad \alpha=\arcsin{b\over a}\ .$$ The area $f(x)$ of the shaded shape is then given by $$f(x)=(\pi-\alpha)a^2+(r-x)b=\left(\pi-\arcsin\sqrt{{2rx\over r^2+x^2}}\right)(r^2+x^2)+(r-x)\sqrt{2rx}\ .$$ Putting $x:=0$ here one gets $f(0)={\pi\over2}$, as expected. Now plotting $f$ for small positive $x$ one finds that $f$ is actually decreasing for $0\leq x\leq 0.3$. But already on a pocket calculator you can verify that, e.g., $f(0.05)\doteq1.56016$, which is $<{\pi\over2}$.

enter image description here

$\endgroup$
  • $\begingroup$ Cool,$f(x)$ is a little complex , maybe I should use math software to get the functional image. $\endgroup$ – lanse2pty May 23 '15 at 1:04
8
$\begingroup$

Here is a somewhat simpler proof that the $1\times\sqrt{2}$ rectangle works (see @Peter Woolfitt 's original answer).

If the rectangle is aligned with the grid it is obvious that it hits a grid point.

enter image description here

Assume that the rectangle is tilted with respect to the grid axes by an angle $\alpha$, whereby $0<\alpha\leq{\pi\over 4}$. The longer sides of the rectangle determine an infinite strip of width $1$, shown in red in the above figure. Each vertical grid line intersects the strip in a segment of length $\ell$ with $1<\ell\leq\sqrt{2}$. Therefore each such line has one or two gridpoints within the strip. The rectangle is lying somewhere in the strip. The euclidean distance between two successive red grid points is $1$ or $\sqrt{2}$; therefore their projected distance on the axis of the strip is $\leq\sqrt{2}$. This shows that the rectangle having length $\sqrt{2}$ will hit a grid point in any case.

$\endgroup$
  • $\begingroup$ So much simpler :D $\endgroup$ – Peter Woolfitt May 30 '15 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.