No Three In Line Problem
Last updated: 4/4/06
How many points
can you place on an NxN grid so that no three of them are in a straight line?
This means any line, not just the
orthogonal grid lines. Well, obviously no row or column can have more than two
points in it, so the answer is never more than 2N. This upper bound is
achievable for small grids; but it is conjectured that there are a finite
number of solutions with 2N points.
I heard
about the problem from Ed Pegg’s Math Games column on chessboard
tasks. Achim Flammenkamp has extensive
notes on this problem, and has computed all solutions for N up to 16, and
the number of solutions in certain symmetry classes for much larger N. He also
has the largest known solution, for N=52. Together these two sources give much
better history and references on the problem than I’ll attempt here. The number
of unique solutions for each N is given in Sloane’s sequence A000769.
Using a
branch-and-bound style recursive search, more modern computers,
and a lot of CPU cycles, I’ve computed all the solutions for N=17 and N=18.
Here is the full sequence, as far as it is known:
|
N |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
|
# of solutions |
1 |
1 |
4 |
5 |
11 |
22 |
57 |
51 |
156 |
158 |
566 |
499 |
1366 |
3978 |
5900 |
7094 |
19204 |
There’s a
sort of limping even-odd phenomenon, but if you plot the number of solutions
for even and odd N separately on a log scale, they form pretty straight lines,
with the exception of the unusually high number for N=15. No sign of a tapering
off yet…
Available
for download are the complete list of solutions for N=17
and N=18. The format is one solution per line,
a list of 2N numbers indicating which points are taken. Points are numbered 0
to N^2-1, left to right, top to bottom. Each solution in these lists is unique,
meaning it is not a rotated or reflected version of some other one. Complete
solutions for smaller N are available (in a different format) on Flammenkamp’s
site.
You can find me at chaffin@gmail.com.