5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @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. $\endgroup$ Feb 11, 2020 at 12:44
  • $\begingroup$ @JaapScherphuis: Yes, you are correct, it is $2\cdot 9+ 1 $ with that argument. $\endgroup$
    – orangeskid
    Feb 12, 2020 at 23:21

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Anvit
    Feb 11, 2020 at 13:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .