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

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.

• @orangeskid I think you misread his proof. He first puts the $13$ points them in $3$ buckets according to the first coordinate only, giving one bucket with at least $5$. The second part of the argument makes use of the fact that you can also use three different coordinate values ($0+1+2$ is also divisible by $3$). This is why it improves on using $9$ buckets directly. BTW, if you directly use 9 buckets (i.e. don't make use of the $0+1+2$ case in the second coordinate) then you need only $2\cdot9+1=19$ elements, not $28$. The question is can the bound be lowered more by using $0+1+2$ on x too. Feb 11, 2020 at 12:44
• @JaapScherphuis: Yes, you are correct, it is $2\cdot 9+ 1$ with that argument. Feb 12, 2020 at 23:21

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.

• I was exactly trying to avoid making multiple cases like. I will wait about a day or two for a purely pigeonhole principle asnwer before marking Feb 11, 2020 at 13:59