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

3
$\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.