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