TOPICS
Search

No-Three-in-a-Line-Problem

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

For 2<=n<=32, it is possible to select 2n lattice points with x,y in [1,n] 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 n=1, 2, ..., are 1, 1, 4, 5, 11, 22, 57, 51, 156 ... (OEIS A000769). For large n, it is conjectured that it is only possible to select at most (c+epsilon)n lattice points with no three collinear, where

c=1/3pisqrt(3)
(1)
approx 1.813799...
(2)

(OEIS A093602; Guy, pers. comm., Oct. 22, 2004), correcting Guy and Kelly (1968) and Guy (1994, p. 242) who found c=(2pi^2/3)^(1/3) approx 1.87.

52x52 No-three-in-a-line

The largest known solution is for n=52, found by Flammenkamp and illustrated above. Flammenkamp gives thousands of solutions for n<52.

See also

Integer Lattice, N-Cluster, Tic-Tac-Toe

Explore with Wolfram|Alpha

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." 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." 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. http://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

Subject classifications