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.
1x1 grid 1 point (trivial)
For larger grids the upper bound is 2x points (since each row/column can only have 2.) I haven't reached this limit for 7 and up. There seem to be multiple solutions for most of these but I'm only including the first I found.
2x2 grid 4 points (trivial)
3x3 grid 6 points (points are X's blanks are O's)
OXX
XOX
XXO
4x4 grid 8 points
OXXO
XOOX
XOOX
OXXO
5x5 grid 10 points
XXOOO
XOOXO
OOOXX
OXXOO
OOXOX
6x6 grid 12 points
OOOXXO
OXOOOX
OOOXOX
XOXOOO
XOOOXO
OXXOOO
7x7 grid 12 points (maximum?)
OOOOXXO
OOXOOOX
OXOOOOX
OOOOOOO
XOOOOXO
XOOOXOO
OXXOOOO (nice ellipse)
8x8 grid 14 points (maximum?)
OOOOOXXO
OOOXOOOX
OOOOOOOX
OXOOXOOO
OOOXOOXO
XOOOOOOO
XOOOXOOO
OXXOOOOO
Thats all for now.

Posted by Jer
on 20050519 17:02:04 