Guaranteeing an integer lattice point centroid

Question

My question is this:

Writing $n(4)$ to be the minimum number of integer lattice points in the plane so that some four of them must determine an integer lattice point centroid, show that $n(4)=13$.

I have shown in a previous exercise by using the pigeonhole principle that among any five distinct integer lattice points the midpoint of some two of them will also be an integer lattice point. This fact is needed to solve the above problem.

Can someone help please?

Update: From the comments below I have succeeded in showing that $n(4)\le 13$. To complete the proof it remains to show that $n(4)>12$. In other words, a set of 12 integer lattice points is needed which avoid having any 4-subset which yields a integer lattice point centroid.

Answer 1

The fact that 13 points is enough to guarantee somed set of four with lattice point centroid has been shown in the comments, thanks to Steve Kass. This answer is hopefully an example of 12 points that don't work, as suggested by hardmath.

EDIT: as hardmath notes in a comment, a previous attempt did not work. This is one that I have checked on maple.

For twelve points which have no subset of 4 with centroid at a lattice point, consider the lattice points:

$$(0,0),\ (0,4),\ (0,8),$$ $$(1,2),\ (1,6),\ (1,10),$$ $$(2,1),\ (2,5),\ (2,9),$$ $$(3,3),\ (3,7),\ (3,11).$$ Note that there are three in each group which are congruent mod $(Z_4)^2$. So another way to look at a computation is to consider three each of the first terms in the four lists, and look at the sums mod $4$.

I did a check of all sets of 4 of the above vertices on maple, to verify that none of the sums have both coordinates $0 \mod 4$, and so none of the centroids are lattice points.

Here is a sketch of how the example can be checked "by hand". Suppose one has the multiset $A=\{ 0,0,0,1,1,1,2,2,2,3,3,3 \}$ of residues mod 4. (three of each residue). There are then only the following six ways to make a sum of $0$ mod $4$ from $A$, and next to each in brackets is the value mod 4 of that sum after interchanging the residues $1$ and $2$:

$0+0+2+2$ : [$2=0+0+1+1$]

$1+1+3+3$ : [$2=2+2+3+3$]

$0+0+1+3$ : [$1=0+0+2+3$]

$1+1+2+0$ : [$2=2+2+2+0$]

$2+2+3+1$ : [$3=1+1+3+2$]

$3+3+0+2$ : [$3=3+3+0+1$]

A look at the four "generating" lattice points $(0,0),(1,2),(2,1),(3,3)$ shows how the generating set was obtained using each residue class mod 4 as first coordinate, and using the first coordinate with 1 and 2 permuted as the second coordinate. Then each of the generating pairs was simply increased mod 4 on the second coordinates to obtain 12 distinct lattice points.

Answer 2

Initially coffeemath and I sought twelve point subsets of a 4x4 grid, such as the following (which turns out to be a "bad example"):

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

This is a natural approach because coordinates of points may be reduced modulo 4 without affecting the integer centroid property. However in doing so, distinct points may be sent to a common image, thus giving fewer than 12 points in the 4x4 grid. coffeemath's example illustrates this, since there are only 4 distinct images when reduced mod 4.

I decided to investigate whether there exists a twelve point subset of these 16 points, free of integer centroid 4-subsets. Although $\binom{16}{12} = 1820$ possibilities exist, with some help from Dan Shved about combining symmetries of the 4x4 grid, these may be reduced to just 33 representative cases. These I could then check by hand: all include 4-point subsets with integer centroids.

Then I investigated the maximum number of points that can be taken from the 4x4 grid without getting such an integer centroid 4-subset. It turns out one can take at most 8 points. Up to the symmetries discussed in the link above, there are only three ways to reach that limit. Below x denotes points included in the subset, however each solution turns out to be symmetric with its complement:

x  x  o  o  |  o  x  x  o  |  o  x  o  x  
x  x  o  o  |  o  o  x  x  |  o  x  o  x  
x  x  o  o  |  x  o  o  x  |  x  o  x  o  
x  x  o  o  |  x  x  o  o  |  x  o  x  o  

The most compact and symmetric 12 point arrangement I found is in a 6x6 grid:

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

None of the 8 point arrangements in a 4x4 grid shown above extends to a 12 point subset of a 5x5 grid, which suggests that there are no feasible 12 point subsets of a 5x5 grid.