Polygon on a grid

Given a square constructed on a grid of points with integer coordinates, what is its maximum area, if we know that there are exactly 3 grid points in its interior?

I have no idea how to start. I googled and found there is a Pick's theorem, but again I don't know how to use it.

Solution 1:

This is AHSME 1998 #29. AoPS threads. The formulation in that contest was multiple choice; which estimate the maximal area was closest to, among $4.0$, $4.2$, $4.5$, $5.0$, and $5.6$. Taking the contest live back in 1998, I'm pretty sure this is one of the five questions I left blank.

You mentioned Pick's theorem. That theorem leads to an area estimate of $4$, from four lattice points at the vertices and three in the interior. But Pick's theorem has a precondition - all vertices must be lattice points. The problem didn't specify that, so the theorem doesn't apply.

I have an argument in one of the linked threads, found by chasing a dead end, that ruled out the largest multiple-choice option.
We take the three points $(0,0)$, $(1,0)$, and $(0,1)$ as our three interior lattice points, so the center of the square is inside that triangle. Then the three closest lattice points outside that triangle must be outside the square, at a distance at least $\frac{s}{2}$ from the center. In the interesting case, these three points will be at $(1,1)$, $(0,-1)$, and $(-1,0)$ - everything else is farther away from the center than one of these points. The circumcenter of those three points is at $(\frac16,\frac16)$, at a distance $\frac56\sqrt{2}$ from each of them. From that, $s \le \frac53\sqrt{2}$.
But wait - that's fitting a circle, not a square. We can only have the distances equal to $\frac s2$ if the three points are at midpoints of sides, forming an isosceles right triangle. They don't, so this extreme is impossible, and $s$ is significantly less than $\frac53\sqrt{2}$, for an area significantly less than $\frac{50}{9}\approx 5.6$.

Then, it's pretty easy to find the configuration with area $4.5$ (@Takahiro Waki's first picture). The configuration with area $5.0$ (@Takahiro Waki's second picture) is harder to find, but it's there.

That's enough to answer the multiple choice problem - which was a genuinely hard problem, for a contest with a time limit of three minutes per problem on average. But we're working to higher standards here; we want to show that the supremum of area is exactly $5$.

Let's go back to those points I mentioned. Assume that $A=(0,0)$, $B=(1,0)$, and $C=(0,1)$ are in the square's interior, so that $(1,1)=D$, $(0,-1)=E$, and $(-1,0)=F$ are on or outside its boundary. Let's name the square as well; call it $Q$. The segments $DE$ and $DF$ pass through the triangle $ABC$, so they pass through $Q$'s interior. Here's a picture, with a version of the area-5 square drawn in:

We can describe every point outside $Q$ as being on one or two sides of $Q$; each of the sides is described by a linear inequality, and we check which of those inequalities are satisfied. We claim that the distance between two points on opposite sides of $Q$ is at least the side length $s$ of $Q$. Why? Because those sides are parallel lines; the shortest distance between points on the two lines is the orthogonal distance between the lines.
Also, if a segment $XY$ ($X,Y$ outside $Q$) intersects $Q$, then $X$ and $Y$ are not on the same side of $Q$. If they were, every point on the segment between them would satisfy the same linear inequality.

So now, we look at our three points $D,E,F$. Which sides are they on? Label the sides in cyclic order $S_1,S_2,S_3,S_4$. WLOG, $D$ is on side $S_1$. Since $DE$ and $DF$ both intersect $Q$, neither $E$ nor $F$ can be on side $S_1$. If either $E$ or $F$ is on side $S_3$, we have that $DE=DF=\sqrt{5}\ge s$ and the area of $Q$ is at most $5$. If one of $E$ and $F$ is on side $S_2$ and the other is on side $S_4$, then $EF=\sqrt{2}\ge s$ and the area of $Q$ is at most $\sqrt{2}$. That leaves only one possibility for an area greater than $5$: both $E$ and $F$ are on the same side $S_2$ (WLOG) of $Q$.

Now, since $D$ is on the opposite side of $S_1$ from $B$ and $C$, line $S_1$ must intersect segments $BD$ and $CD$ without touching $B$ or $C$. As such, it has negative slope. Similarly, line $S_2$ must intersect segments $AE$ and $AF$ without touching $A$, so it has negative slope as well. But $S_1$ and $S_2$ are perpendicular; if one has negative slope, the other must as well. This is a contradiction, and this configuration is impossible.

With that case ruled out, the area is at most $5$. We have already demonstrated that an area of exactly $5$ is possible, and we're done.