TOPICS
No-Three-in-a-Line-Problem
For
, it is possible to select
lattice points with![x,y in [1,n]](/image.pl?url=http%3a%2f%2fmathworld.wolfram.com%2fimages%2fequations%2fNo-Three-in-a-Line-Problem%2fInline3.svg&f=jpg&w=240)
such that no three are in a straightline (where "straight line" meansany 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 ... (OEISA000769). For large
, it is conjectured that it is only possible to select at most
lattice points with no threecollinear, where
 |  |  | (1) |
 |  |  | (2) |
(OEISA093602; 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-ToeExplore with Wolfram|Alpha
References
Adena, M. A.; Holton, D. A.; and Kelly, P. A. "Some Thoughts on the No-Three-In-Line Problem." InCombinatorial 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. A60, 305-311, 1992.Flammenkamp, A. "Progress in the No-Three-In-Line Problem. II."J. Combin. Th. Ser. A81, 108-113, 1998.Flammenkamp, A. "The No-Three-in-Line Problem."http://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." InCombinatorial 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 inUnsolved 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.http://www.maa.org/editorial/mathgames/mathgames_04_11_05.html.Sloane, N. J. A. SequencesA000769/M3252 andA093602 in "The On-Line Encyclopedia of Integer Sequences."Referenced on Wolfram|Alpha
No-Three-in-a-Line-ProblemCite this as:
Weisstein, Eric W. "No-Three-in-a-Line-Problem."FromMathWorld--A Wolfram Resource.https://mathworld.wolfram.com/No-Three-in-a-Line-Problem.html