Sum of areas of triangles which have corners which are lattice points with 74 lattice points inside.

Question

Here is a problem I was given: A lattice point in the plane is a point whose coordinates are both integers. Consider a triangle whose vertices are lattice points (0,0),(a,0) and (0,b), where b≤a. Suppose the triangle contains exactly 74 lattice points in its interior, not including those lattice points on the sides of the triangle. Determine the sums of the areas of all such triangles. The only way that I could see to do this problem was to try all possible values of a, checking to see which values of b gave 74 lattice points. I did this and gave up at a=5 so I suspect there must be an easier way. I was thinking Pick's theorem would be useful but I couldn't think of what to do with it. Can anyone provide a shortcut, or at least just give me the answer? By the way, I know it is less than 1000.

Answer 1

Pick's theorem definitely seems like the way to go. We have to figure out how many lattice points are on the boundary, and the hypotenuse is the only nontrivial side to consider. You should convince yourself, perhaps by considering the slope of the hypotenuse and when it can go through lattice points, that the number of lattice points on the hypotenuse (not counting the vertices) is $\gcd(a,b)-1$. So Pick's theorem says that you're looking for triangles such that $$ 74 + \frac{a+b+\gcd(a,b)}2 - 1 = \text{area} = \frac{ab}2, $$ or $$ 146 = ab-a-b+\gcd(a,b). $$ Since the right-hand side is divisible by $\gcd(a,b)$, that gcd must be either 1, 2, 73, or 146. Now rearrange into $$ 147-\gcd(a,b) = ab-a-b+1 = (a-1)(b-1). $$ One quickly rules out the gcd equaling 73 or 146, and so there are two cases.

Case 1: $\gcd(a,b)=1$ and $146 = (a-1)(b-1)$. There are only two factorizations of $146$ to try, and they both work: $\{a,b\} = \{147,2\}$ and $\{a,b\} = \{74,3\}$.

Case 2: $\gcd(a,b)=2$ and $145 = (a-1)(b-1)$. Again there are only two factorizations of $145$, and now only one works: $\{a,b\} = \{146,2\}$ is good, but $\{a,b\} = \{30,6\}$ has the wrong gcd.

So there are six triangles in all, with total area $2(\frac12147\cdot2 + \frac1274\cdot3 + \frac12146\cdot2) = 808$.

Answer 2

There are exactly three such triangles from an exhaustive search: $$(a,b) = \{(150, 2),(149, 2),(38, 5)\}$$

with areas $150,149 $ and $95$ for a total of $394$.

For a non-search approach, we can build on Christian Blatter's observation that the $(a,b)$ rectangle has $(a-1)(b-1)$ (interior) lattice points and given $d =\gcd(a,b)$, it has $(d-1)$ points on its diagonal, giving the requirement here that
$$\begin{align}2\cdot 74 &= (a-1)(b-1)-(d-1) \\ 148 &= ab-a-b+1-d+1 \\ 146 &= ab-a-b-d \\ \end{align}$$

Since $d \mid a,b$, this means $d\mid 146 = 2\cdot 73$, and it's apparent that we need $b<14$, so $d = 1$ or $2$.

$d=2 \implies (a-1)(b-1) = 149$ (prime) giving $(a,b) =(150,2)$

$d=1 \implies (a-1)(b-1) = 148 = 2^2\cdot 37$ giving $(a,b) = \{(149,2),(38,5)\}$, with $(75,3)$ disqualified for $\gcd(75,3) = 3$.