Progress in the no-three-in-line-problem (Q1193582)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Progress in the no-three-in-line-problem |
scientific article |
Statements
Progress in the no-three-in-line-problem (English)
0 references
27 September 1992
0 references
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.
0 references
grid
0 references
Euclidean plane
0 references
no-three-in-line-problem
0 references
conjecture of Kelley
0 references
orthogonal reflection symmetry
0 references