Progress in the no-three-in-line-problem
type: Item
instance of: scholarly article
title: Progress in the no-three-in-line-problem
zbMATH Open document ID: 0774.05025
DOI: 10.1016/0097-3165(92)90012-J
author: Achim Flammenkamp
published in: Journal of Combinatorial Theory. Series A
publication date: 1992-09-27T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05B30
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 64867
zbMATH Keywords: grid
zbMATH Keywords: Euclidean plane
zbMATH Keywords: no-three-in-line-problem
zbMATH Keywords: conjecture of Kelley
zbMATH Keywords: orthogonal reflection symmetry
reviewed by: Bernd Richter
MaRDI profile type: Publication
cites work: Q4067112
cites work: Q4769056
cites work: Update on the no-three-in-line problem
cites work: On the no-three-in-line problem
cites work: The No-Three-In-Line Problem
cites work: Some advances in the no-three-in-line problem
cites work: No-three-in-line for seventeen and nineteen
cites work: On the no-three-in-line problem. II
cites work: On the no-three-in-line problem. III
cites work: On a Problem of Heilbronn
full work available at URL: 0097-3165(92)90012-j
OpenAlex ID: W4213108673
Recommended article: Progress in the no-three-in-line problem. II
Recommended article: The extensible no-three-in-line problem
Recommended article: Q5243818
Recommended article: Applying iterated mapping to the no-three-in-a-line problem
Recommended article: A note on the no-three-in-line problem on a torus
Recommended article: On no-three-in-line problem on \(m\)-dimensional torus
Recommended article: No-three-in-line problem on a torus: periodicity
Recommended article: The linear ordering problem revisited
Recommended article: Martin Gardner’s Minimum No-3-in-a-Line Problem
description: scientific article; zbMATH DE number 64867