HMMT November

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 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$.