center of mass of triangle

We arbitrarily choose n lattice points in a 3-dimensional Euclidean space such that no three points are on the same line. What is the least n in order to guarantee that there must be three points x, y, and z among the n points such that the center of mass of the x-y-z triangle is a lattice point?

-
Still thinking about this; but I've got an upper bound for $n$, namely 55. Consider the congruence classes mod 3 of each of the 3 co-ordinates of a point. For any given point, there are 27 possibilities for the congruence class of each co-ordinate. So if we have 55 points, then the pigeonhole principle implies that there are 3 for which each of the three co-ordinates are congruent mod 3. Those 3 points for a triangle whose centroid is a lattice point. However, I feel that the real answer is way less than 55; I'm still thinking about it. – user22805 Sep 25 '12 at 4:54
Is the center of mass simply the average of the three vertices? – Gerry Myerson Sep 25 '12 at 5:50
Is this question already answered at math.stackexchange.com/questions/125479/… ? – Gerry Myerson Sep 25 '12 at 5:52
There's a useful if inconclusive discussion at forums.philosophyforums.com/threads/… – Gerry Myerson Sep 25 '12 at 5:55
A lower bound for $n$ is 17. Still considering congruence classes mod 3 of the co-ordinates, choose the 8 combinations of congruence classes where no coordinate $\equiv 2$ mod 3. Choose two points with each of these 8 combinations. Then of those 16 points, no 3 of them make a triangle. So $n$ must be at least 17, and by my earlier comment, at most 55. – user22805 Sep 25 '12 at 5:58

2 Answers

19 according to "A lattice point problem and additive number theory" and its references

-
Here is a link: cs.tau.ac.il/~nogaa/PDFS/centroid.pdf – Matthew Conroy Sep 25 '12 at 6:00

The answer $19$ has already been given, including references, so this is just a numerical check of that result.

The specific shape of the lattice is irrelevant, since a point is a lattice point iff it is an integer linear combination of the lattice vectors. The centre of mass of three lattice points is a lattice point iff all coefficients of the sum are multiples of $3$.

To find the maximal number of points without a centre of mass on the lattice, consider the distribution of the residues of the coefficients of the points $\bmod3$ in $\mathbb Z_3^3$. No three points may add up to $0\in\mathbb Z_3^3$.

We cannot have the same point in $\mathbb Z_3^3$ three times. On the other hand, whatever points in $\mathbb Z_3^3$ we do have, we can have them twice, since the only point that would sum to $0$ with the two copies would be a third copy. Thus, we can reduce the problem to finding the maximal number of different points in $\mathbb Z_3^3$ no three of which add up to $0$; then the desired maximal number of not necessarily different points is twice that.

Here's code that enumerates all subsets of $\mathbb Z_3^3$ and finds the maximal size of a subset that doesn't contain a triple that sums to $0$. That maximal size turns out to be $9$, so the maximal size of a set of not necessarily different points is $2\cdot9=18$. Thus one more than that, $19$, is the number of points required to force a set to contain a triple with centre of mass on the lattice.

-
Thanks to all. My best guess is also 9+9+1, but, is there another way to explain "9"? – lincy Sep 26 '12 at 4:39