Imagine a 3 dimensional grid with N x N x N points.
Place as many points as possible on this grid, such that there are no 3 points in a line (for N = 2, this is of course 8).
How much is it for N = 3, 4 or 5?

(In reply to N=3? by Jer)

I can prove that you have reached the maximum number of points for N=3.

Now there are 3 layers, and each can have no more than 6 points, making the theoretical max an 18.  If we want to beat 16 points, two of the layers must have 6 and the other must have 5.  One of the layers with 6 must be the top or bottom layer, and it must be arranged like this:

0**
*0*
**0

One of the other two layers must also have 6 points.  However, there are only a few cases to try, so brute force will show that after having any two layers with 6 points, the third cannot have 5.

This means it is time to move on to N=4 and 5.

Posted by Tristan on 2005-05-08 02:20:43