Lattice Points

Each integer is either odd or even. Thus there are four parity classes in $\mathbb{Z}^2$ (one where both components are odd, one where both components are even, and two where the two components have opposite parities). Thus, if we have $5$ or more members of $\mathbb{Z}^2$ , then there must exist at least two of them that belong to the same parity class, so that their mean is a lattice point.

If we have a set $S$ of $13$ lattice points, we can find two points $x_1,x_2 \in S$ such that $\tfrac12(x_1+x_2)$ is a lattice point. Then $S_1 = S \backslash \{x_1,x_2\}$ has $11$ points, and hence we can find two points $x_3,x_4 \in S_1$ such that $\tfrac12(x_3+x_4)$ is a lattice point. Then $S_2 =S_1 \backslash \{x_3,x_4\} = S \backslash \{x_1,x_2,x_3,x_4\}$ has $9$ points, so we can find two points $x_5,x_6 \in S_2$ such that $\tfrac12(x_5+x_6)$ is a lattice point. Then $S_3 = S \backslash\{x_1,x_2,x_3,x_4,x_5,x_6\}$ has $7$ points, so we can find two points $x_7,x_8 \in S_3$ such that $\tfrac12(x_7+x_8)$ is a lattice point. Finally $S_4 = S \backslash \{x_1,x_2,x_3,...,x_8\}$ has $5$ points, so we can find two points $x_9,x_{10} \in S_4$ such that $\tfrac12(x_9+x_{10})$ is a lattice point.

Thus we have found $10$ distinct points in $S$ such that the averages $\tfrac12(x_1+x_2)$ , $\tfrac12(x_3+x_4)$ , $\tfrac12(x_5+x_6)$ , $\tfrac12(x_7+x_8)$ and $\tfrac12(x_9 + x_{10})$ are lattice points. But then there must exist two of these five averages which belong to the same parity class, and so such that the average of these two averages is a lattice point. In other words, we can find four points in $S$ such that their centroid is a lattice point.

On the other hand, it is possible to find a set of $12$ lattice points, no four of which have a centroid which is a lattice point. Consider the four sets $\begin{aligned} C_0 & = \; \big\{(4a,4b) \,|\; a,b \in \mathbb{Z}\big\} \\ C_1 & = \; \big\{(4a+1,4b+2) \,|\; a,b \in \mathbb{Z}\big\} \\ C_2 & = \; \big\{(4a+2,4b+1) \,|\; a,b \in \mathbb{Z}\big\} \\ C_3 & = \; \big\{(4a+3,4b+3) \,|\; a,b \in \mathbb{Z}\big\} \end{aligned}$ and consider any set $\hat{S}$ with $12$ elements comprising three elements from each of these sets.

Suppose that we can find a subset of $4$ elements of $\hat{S}$ whose centroid is a lattice point. Then we are going to pick $a$ elements from $C_0$ , $b$ elements from $C_1$ , $c$ elements from $C_2$ and $d$ elements from $C_3$ , which means that $a,b,c,d$ are integers such that $0 \le a,b,c,d \le 3$ , $a+b+c+d = 4$ , and $b + 2c + 3d \equiv 2b + c + 3d \equiv 0 \pmod{4}$ This implies that $b \equiv c \pmod{4}$ , and hence that $b=c$ . Thus $3(b+d) \equiv 0 \pmod{4}$ and hence $d \equiv 4-b \pmod{4}$ . If $b > 0$ this means that $d=4-b$ , and hence $4 = a+b+c+d = a+b+4 > 4$ , which is impossible. Thus $b=0$ , which implies that $d=0$ . But then $a=4$ , which is impossible. Thus we have shown that no collection of four elements of $\hat{S}$ has a centroid which is a lattice point. Thus $\boxed{12}$ is the desired answer.