For , it is possible to select lattice points with 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 ... (Sloane's A000769). For large , it is conjectured that it is only possible to select at most lattice points with no three collinear, where

			(1)
			(2)

(Sloane's 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 .

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."

CITE THIS AS:

Weisstein, Eric W. "No-Three-in-a-Line-Problem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/No-Three-in-a-Line-Problem.html