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 2005-05-19 17:02:04