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
solution.
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
following
"empty"
"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
below:
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