Center of Gravity With Integer Coordinates

Does there exist a number N such that any set of N or more points
with integer coordinates in 3D space must contain the vertices of a
triangle whose center of gravity also has integer coordinates?  If
so, what is that number?

First, a triangle's center of gravity has all integer coordinates iff 
the sum of the x coordinates, the sum of the y coordinates, and the 
sum of the z coordinates of the three vertices are each divisible by 
3 (so all three averages are integers).  This shows that we really 
only need to consider coordinates modulo 3, and the coordinates of 
each point can be represented by one of the 27 three-digit numbers 
000 to 222 in base 3.

Next, notice that if two of the vertices of a triangle have 
coordinates of the same form "abc", then the only way for the CG 
to have all integer coefficients is if the third vertex is also 
of the form "abc".  Thus, no form can appear in the set more than 
twice, and there is no need for any form to appear less than 
twice, so each form in a maximal set will appear exactly twice.  
(This already limits the total number of points to be no greater 
than 54.)

At this point we might try a brute force search, starting with all 27 
types and discarding some until we arrive at a set with no integer
CGs.  When we find such a set, we could check each excluded type, one 
at a time, to see if any could be added without giving any integer CGs.
This approach will give a "locally maximal" solution set, but it will
not necessarily give a global maximal set.  For example, the 16-point 
set with the types

             001  002  012  101  112  122  211  221

is maximal in the sense that it has no integer CGs, and if you add 
any other vertex type to the set, it introduces integer CGs.  However, 
this is not the largest possible solution set.

One way of approaching the global solution is to associate each vertex 
"xyz" with a cell in the following matrix

                             0  1  2

                        0    a  b  c
                        1    d  e  f
                        2    g  h  i

where the x coordinate corresponds to the vertical index and the y
coordinate corresponds to the horizontal index.  Then all we need to 
do is determine the allowable z coordinates in each cell of the array.
The locally maximal solution set given earlier is represented by the
assignments shown below

                              0    1    2

                        0    1,2   2   
                        1     1    2    2
                        2          1    1

Here there are actually two z values assigned to one cell, and two 
cells are empty.  It can be verified that adding any z value to any 
cell will result in either "three-in-a-row" or in a "0-1-2" straight, 
so this set can't be increased, and yet it's not the best possible 

Notice that the x and y coordinates of the CG of a given triangle 
will both be integers iff the three vertices are taken from a 
vertical, horizontal, or diagonal row of this array (including 
wrap-around diagonals such as c-d-h), or all from the same cell.  
Therefore, if we assign one z value to each cell such that they 
are not all the same nor all different along any vertical, 
horizontal, or diagonal line, then the result will be a solution 
set.  An example is shown below

                             0  1  2

                        0    0  0  1
                        1    0  0  1
                        2    1  1  2

This represents an 18-point set with the nine vertex types

               000  010  021  100  110  121  201  211  222

Intuitively it seems impossible to place 10 or more z values in the 
9 cells without allowing either "three-in-a-row" or a "straight".   
This can be confirmed by evaluating all possible assignments of z 
values.  Notice that the contents of each cell must be one of the 

     "0"         "1"         "2"
     "0 and 1"   "0 and 2"   "1 and 2"

so there are 40,353,607 arrangements to check.  Of these, only 122419
yield non-integer CGs.  The numbers of distinct vertex types in these
solution sets are summarized below:

         number of distinct       number of
         vertex types             occurrences
        -------------------      ------------
                 0                      1        (3^0)
                 1                     27        (3^3)
                 2                    351        (3^3)(13)
                 3                   2592   (2^5)(3^4)
                 4                  11178     (2)(3^5)(23)
                 5                  27864   (2^3)(3^4)(43)
                 6                  39744   (2^6)(3^3)(23)
                 7                  30456   (2^3)(3^4)(47)
                 8                  10044   (2^2)(3^4)(31)
                 9                    162     (2)(3^4)
                        total      122419

The 162 cases with 9 vertex types (each of which yields an 18-point 
solution set) occur in the following 6 arrangements:

   I.    0 0 1        II.   0 1 1       III.   0 0 1
         0 0 1              1 0 1              1 0 0
         1 1 2              0 0 2              1 2 1

   IV.   0 1 0         V.   0 0 1       VI.    0 1 0
         0 1 0              1 2 1              1 2 1
         1 2 1              1 0 0              0 1 0

Allowing for rotations, reflections, and permutations of {0,1,2}, 
these six arrangements yield the numbers of distinct sets listed 
                      I.  24
                     II.  48
                    III.  48
                     IV.  24
                      V.  12
                     VI.   6
                  total  162

So to answer the original question, I think if you have 19 or more 
distinct points with integer (orthogonal) coordinates in 3D space,
you are assured that at least one triangle formed from three of
those point has a CG with all integer coefficients.  For any n less 
than 19 it's possible to construct a set of n points such that no 
triangle has an integer CG.

Return to MathPages Main Menu