For any grid, x by x, figure out a formula for the greatest number of points that can be put on the inside of the grid such that no three points are colinear.

http://mathworld.wolfram.com/No-Three-in-a-Line-Problem.html

There is a sequence for the number of possibilities for each n.

It is a little suprising the number of solutions with 2n points increases rapidly given they get so hard to find.  Its also suprising to see it conjectured that for large grids the upper limit is only about 1.87n

I can't imagine the run-times for programs searching for large cases.

Also a note to McWorter:  to keep you post from skipping lines when you hit enter, use shift-enter. 

Posted by Jer on 2005-05-20 12:09:20