Problem 42765. Maximize Non-Co-Planar Points in an N-Cube
This Challenge is to find a set with the maximum number of integer points that create planar surfaces with a maximum of three points from the set. No four points may be co-planar. Given the size N and the number of expected points Q find a set of Q points. Only N=2/Q=5 and N=3/Q=8 will be tested. N=4/Q=10 or N=5/Q=13 are too large to process.
N=2 contains 8 points [0,0,0;0,1,0;1,0,0;1,1,0;0,0,1;0,1,1;1,0,1;1,1,1] N=3 contains 27 points [0,0,0;0,0,1;0,0,2;...2,2,2]
Output is a Qx3 matrix of the non-co-planar points.
Reference: The March 2016 Al Zimmermann Non-Coplanar contest is N=primes less than 100. Maximize the number of points in an NxNxN cube with no 4 points in a common plane.
Theory: The N=2 and N=3 cases can be processed by brute force if care is taken. Assumption of [0,0,0] greatly reduces number of cases. Solving Cody Co-Planar Check may improve speed.
Solution CommentsShow comments
Problem Recent Solvers6