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?

  • 1
    $\begingroup$ 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. $\endgroup$ – user22805 Sep 25 '12 at 4:54
  • $\begingroup$ Is the center of mass simply the average of the three vertices? $\endgroup$ – Gerry Myerson Sep 25 '12 at 5:50
  • $\begingroup$ Is this question already answered at math.stackexchange.com/questions/125479/… ? $\endgroup$ – Gerry Myerson Sep 25 '12 at 5:52
  • $\begingroup$ There's a useful if inconclusive discussion at forums.philosophyforums.com/threads/… $\endgroup$ – Gerry Myerson Sep 25 '12 at 5:55
  • $\begingroup$ 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. $\endgroup$ – user22805 Sep 25 '12 at 5:58

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

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\begingroup$ Thanks to all. My best guess is also 9+9+1, but, is there another way to explain "9"? $\endgroup$ – lincy Sep 26 '12 at 4:39

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.