Minimum number of lattice points required so that there exists three points whose mean is also a lattice point

Question

I proved via pigeonhole principle that $5$ is enough is if we're taking mean of two points. Define a function which maps the lattice point to its modular class in $\mathbb Z_2\times \mathbb Z_2$, then atleast one of the classes will have 2 points and hence we are done.

I am looking for a similar proof in which we preferably only apply the pigeonhole principle once. I know $13$ works by repeated applications of pigeonhole, but I don't know if $12$ doesn't work out.

The proof for $13$ goes as follows. Define $f:\mathbb N\times\mathbb N$ as $f(x,y)=x(mod \,\,3)$. Then atleast one of the classes will have $5$ elements. Then consider those $5$ points only. We are distribution the $5$ points in $3$ classes (based on second coordinate) thus either all classes have atleast $1$ element or one class has $3$ elements and hence we done.

Answer 1

I think that $9$ lattice points is sufficient. I don't have a pure pigeonhole proof.

Map the points to $\mathbb{Z}/3 \times \mathbb{Z}/3$ by reducing the coordinates modulo $3$. Think of these as a $3\times3$ array of buckets that we put the points into. How many lattice points can we put in there, while still avoiding creating a triplet that has a mean that is also a lattice point?

Such a triplet can be formed in several ways:

• 3 in a row (i.e. non-empty buckets in a row)
• 3 in a column (i.e. non-empty buckets in a row)
• 3 on a diagonal, including broken diagonals (i.e. non-empty buckets on a diagonal)
• 3 in the same bucket

After a bit of trial and error, the first three conditions force at least 5 buckets to be empty, at most 4 non-empty. As soon as you have 5 non-empty buckets, some row, column, or diagonal has only non-empty buckets. This is a bit hard to see, but it helps that you can freely permute the rows or columns to reduce the number of cases you need to check. The only arrangements of 4 non-empty buckets (up to row/column permutation, rotation, reflection) that are possible are:

x x o    x x o    x x o
o o x    x x o    x o x
o o x    o o o    o o o

So you can have at most 4 buckets, each with 2 points, before adding an extra lattice point gives you a triplet. So any set of 9 lattice points will have a triplet whose mean is a lattice point.