Progress in the no-three-in-line-problem (Q1193582): Difference between revisions

Consider a square \(n\times n\) grid in the Euclidean plane. The task is to mark as many of the intersection ponits as possible under the condition that no three of the marked points lie in a straight line. One can obviously mark at most \(2n\) points. The problem of finding for which \(n\) this value is reached is known as the no-three-in-line-problem. Using massive computer power (in days of running time) the author gives new solutions to the problem for \(n=11, 12,\dots,32, 34, 35, 36, 38, 40, 42, 44, 46\). He classifies the resulting patterns of points according to symmetries. So, he generalizes a conjecture of Kelley to: There exist exactly five solutions having orthogonal reflection symmetry. Looking at the authors table 1, the number of solutions seems to increase with \(n\), but an argument of R. Guy and P. Kelley implies that there are no solutions for \(n>600\). An appendix gives pictorial versions of a few of the examples.