HMMT November, 2023

Solution:

We instead choose points $(0,0)$, $(1,0)$, $(a, b)$, $(c, d)$ with $0 \leq a, c \leq 59$ and $0 \leq b, d \leq 5$ with $(c, d)$ in the interior of the triangle formed by the other three points. Any selection of these four points may be connected to form a concave quadrilateral in precisely three ways.

Apply Pick's theorem to this triangle. If $I$ is the count of interior points, and $B$ is the number of boundary lattice points, we have that the triangle's area is equal to

$$\frac{b}{2} = I + \frac{B}{2} - 1$$

Let's first compute the number of boundary lattice points on the segment from $(0,0)$ to $(a, b)$, not counting $(0,0)$. This is just $\operatorname{gcd}(a, b)$. Similarly, there are $\operatorname{gcd}(a-1, b)$ boundary lattice points from $(1,0)$ to $(a, b)$. Adjusting for the overcounting at $(a, b)$, we have

$$B = \operatorname{gcd}(a, b) + \operatorname{gcd}(a-1, b) - 1$$

and thus

$$I = \frac{b - \operatorname{gcd}(a, b) - \operatorname{gcd}(a-1, b) + 1}{2}$$

which we notice is periodic in $a$ with period $b$. That is, the count of boundary points does not change between choices $(a, b)$ and $(a+b, b)$.

We wanted to find the sum across all $(a, b)$ of $I$, the number of interior points $(c, d)$. Using casework on $b$, the periodicity allows us to just check $I$ across points with $0 \leq a < b$, and then multiply the count by $\frac{60}{b}$ to get the sum of $I$ across the entire row of points.

For $b=1,2$, we always have $I=0$.

For $b=3$, we have $I=0$ at $(0,3)$, $(1,3)$ and $I=1$ for $(2,3)$. Using periodicity, this $y$-coordinate has a total of

$$(0+0+1) \cdot \frac{60}{3} = 20$$

For $b=4$, we have $I=0$ at $(0,4)$ and $(1,4)$, and $I=1$ at both $(2,4)$ and $(3,4)$. Using periodicity, this $y$-coordinate has a total of

$$(0+0+1+1) \cdot \frac{60}{4} = 30$$

For $b=5$, we have $I=0$ at $(0,5)$, $(1,5)$ and $I=2$ at $(2,5)$, $(3,5)$, $(4,5)$. Using periodicity, this $y$-coordinate has a total of

$$(0+0+2+2+2) \cdot \frac{60}{5} = 72$$

Adding our cases, we have $20+30+72=122$ ways to choose the four points. Multiplying back by the number of ways to connect the quadrilateral gives an answer of $122 \cdot 3 = 366$.