No-three-in-line problem - Wikipedia
Jump to content
Search
Search
Donate
Create account
Log in
Personal tools
Donate
Create account
Log in
No-three-in-line problem
3 languages
Español<br>Русский<br>ไทย
Edit links
From Wikipedia, the free encyclopedia
Geometry problem on grid points
Unsolved problem in mathematics
How many points can be placed in an n-by-n grid so that no three of them lie on a line?
More unsolved problems in mathematics
A set of 20 points in a 10 × 10 grid, with no three points in a line<br>The no-three-in-line problem in discrete geometry asks how many points can be placed in the
{\displaystyle n\times n}
grid so that no three points lie on a straight line. The problem concerns lines of all slopes, not only those aligned with the grid. It was introduced by Henry Dudeney in 1900. Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points".[1]
At most
{\displaystyle 2n}
points can be placed, because
{\displaystyle 2n+1}
points in a grid would include a row of three or more points, by the pigeonhole principle. Although the problem can be solved with
{\displaystyle 2n}
points for every
{\displaystyle n}
up to
64
{\displaystyle 64}
, it is conjectured that fewer than
{\displaystyle 2n}
points can be placed in grids of large size. Known methods can place linearly many points in grids of arbitrary size, but the best of these methods place slightly fewer than
1.5
{\displaystyle 1.5n}
points, not
{\displaystyle 2n}
Several related problems of finding points with no three in line, among other sets of points than grids, have also been studied. Although originating in recreational mathematics, the no-three-in-line problem has applications in graph drawing and to the Heilbronn triangle problem.
Small instances<br>[edit]
abcdefgh8
877665544332211abcdefghSolution to Dudeney's puzzle of placing 16 pawns on a chessboard such that no three pawns lie on the same line, with two pawns on squares d4 and e5.
120 points in a 60 x 60 grid with no three in a line, and the lines through each pair of points<br>The problem was first posed by Henry Dudeney in 1900, as a puzzle in recreational mathematics, phrased in terms of placing the 16 pawns of a chessboard onto the board so that no three are in a line.[2] This is exactly the no-three-in-line problem, for the case
{\displaystyle n=8}
.[3] In a later version of the puzzle, Dudeney modified the problem by asking for a solution in which two of the pawns are on squares d4 and e5, attacking each other in the center of the board.[4]
Many authors have published solutions to this problem for small values of
{\displaystyle n}
,[5] and by 2026 it was known that
{\displaystyle 2n}
points could be placed on an
{\displaystyle n\times n}
grid with no three in a line<br>for all
{\displaystyle n}
up to
64
{\displaystyle n=64}
.[6] The numbers of solutions with
{\displaystyle 2n}
points for small values of
{\displaystyle n}
, starting from
{\displaystyle n=2}
, are
1, 2, 11, 32, 50, 132, 380, 368, 1135, 1120, 4348, 3622, 10568, ... (sequence A000755 in the OEIS).
The numbers of equivalence classes of solutions with
{\displaystyle 2n}
points under reflections and rotations are
1, 1, 4, 5, 11, 22, 57, 51, 156, 158, 566, 499, 1366, ... (sequence A000769 in the OEIS).[3]
Upper and lower bounds<br>[edit]
The exact number of points that can be placed, as a function of
{\displaystyle n}
, is not known. However, both proven and conjectured bounds limit this number to within a range proportional to
{\displaystyle n}
General placement methods<br>[edit]
Suboptimal placement of 11 points in 12 × 12 grid, using the method of Erdős. The largest prime p less than the grid size is 11; the solution places points at coordinates (i,i2 mod p) for i = 0, 1, ... p − 1. For instance, (4,5) is included because 42 is congruent to 5 mod 11.<br>A solution of Paul Erdős, published by Roth (1951), is based on the observation that when
{\displaystyle n}
is a prime number, the set of
{\displaystyle n}
grid points
{\displaystyle (i,i^{2}}
mod
{\displaystyle n)}
, for
{\displaystyle 0\leq i
, contains no three collinear points. When
{\displaystyle n}
is not prime, one can perform this construction for a
{\displaystyle p\times p}
grid contained in the
{\displaystyle n\times n}
grid, where
{\displaystyle p}
is the largest prime that is at most
{\displaystyle n}
. Because the gap between consecutive primes is much smaller than the primes themselves,
{\displaystyle p}
will always be close to
{\displaystyle n}
, so this method can be used to place
{\displaystyle n-o(n)}
points in the
{\displaystyle n\times n}
grid with no three points collinear.[7]
Erdős' bound has been improved subsequently: Hall et al. (1975) show that, when
{\displaystyle n/2}
is prime, one can obtain a solution with
{\displaystyle 3(n-2)/2}
points, by placing points in multiple copies of the...