No-Three-in-a-Line-Problem
For 
, it is possible to select
lattice points with ![x,y in [1,n]](/images/equations/No-Three-in-a-Line-Problem/Inline3.gif)
such
that no three are in a straight line (where "straight
line" means any line in the plane--not just a horizontal or vertical
line). The number of distinct solutions (not counting reflections and rotations)
for 
, 2, ..., are 1, 1, 4, 5, 11, 22, 57,
51, 156 ... (OEIS A000769). For large 
, it is conjectured that it is only possible
to select at most 
lattice
points with no three collinear, where
(OEIS A093602; Guy, pers. comm., Oct. 22, 2004), correcting Guy and Kelly (1968) and Guy (1994, p. 242) who found 
.
The largest known solution is for 
, found by Flammenkamp
and illustrated above. Flammenkamp gives thousands of solutions for 
.
SEE ALSO: Integer Lattice,
N-Cluster,
Tic-Tac-Toe
REFERENCES:
Adena, M. A.; Holton, D. A.; and Kelly, P. A. "Some Thoughts on the No-Three-In-Line Problem." In Combinatorial
Mathematics: Proceedings of the International Conference on Combinatorial Theory,
Canberra, August 16-27, 1977, pp. 6-17, 1974.
Flammenkamp, A. "Progress in the No-Three-In-Line Problem." J. Combin.
Th. Ser. A 60, 305-311, 1992.
Flammenkamp, A. "Progress in the No-Three-In-Line Problem. II." J. Combin.
Th. Ser. A 81, 108-113, 1998.
Flammenkamp, A. "The No-Three-in-Line Problem." https://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html.
Gardner, M. Penrose Tiles and Trapdoor Ciphers... and the Return of Dr. Matrix, reissue ed.
New York: W. H. Freeman, p. 69, 1989.
Guy, R. K. "Unsolved Combinatorial Problems." In Combinatorial Mathematics and Its Applications: Proceedings of a conference held at the Mathematical
Institute, Oxford, from 7-10 July, 1969 (Ed. D. J. A. Welsh).
New York: Academic Press, pp. 121-127, 1971.
Guy, R. K. "The No-Three-in-a-Line Problem." §F4 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 240-244,
1994.
Guy, R. K. and Kelly, P. A. "The No-Three-in-Line-Problem." Canad.
Math. Bull. 11, 527-531, 1968.
Guy, R. K. and Kelly, P. A. "The No-Three-Line Problem." Research Paper 33, Department of Mathematics, Univ. of Calgary, Calgary, Alberta, Jan. 1968.
Pegg, E. Jr. "Math Games: Chessboard Tasks." Apr. 11, 2005. https://www.maa.org/editorial/mathgames/mathgames_04_11_05.html.
Sloane, N. J. A. Sequences A000769/M3252 and A093602 in "The On-Line Encyclopedia
of Integer Sequences."
Referenced on Wolfram|Alpha:
No-Three-in-a-Line-Problem
CITE THIS AS:
Weisstein, Eric W. "No-Three-in-a-Line-Problem."
From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/No-Three-in-a-Line-Problem.html
Contact the MathWorld Team
incidence
