Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!m.cs.uiuc.edu!news
From: reingold@emr.cs.uiuc.edu (Edward M. Reingold)
Newsgroups: comp.theory
Subject: Re: Non-collinear points on a grid.
Message-ID: <1991Mar8.232545.15265@m.cs.uiuc.edu>
Date: 8 Mar 91 23:22:44 GMT
References: <64124@eerie.acsu.Buffalo.EDU>
Sender: news@m.cs.uiuc.edu (News Database (admin-Mike Schwager))
Organization: University of Illinois at Urbana-Champaign
Lines: 27
In-Reply-To: ajay@cs.Buffalo.EDU's message of 8 Mar 91 23:05:08 GMT

This is an old problem, going back at least to the early part of this century.

Given an $n \times n$ array of $n^2$ points of the unit lattice, what is the
largest number $T(n)$ of the points that can be chosen so that no three are on
a line (``line'' here means vertical or horizontal, not diagonal)?  Clearly
$T(n) \leq 2n$ and $T(n)$ is known to equal $2n$ for $n \leq 24$.  It is also
known that $T(n) > (3/2 - \epsilon)n$ for all $\epsilon >0$.

The problem can be generalized to an $n \times m$ grid.

A related problem is to determine the smallest number of points in the $n
\times n$ grid, no three in a line, such that the set of lines they determine
covers all $n^2$ points of the grid.

This problem was in Martin Gardner's Mathematical Games column of Scientific
American in May, 1972, October, 1976, and March, 1977.  There are many papers
in the literature; see, for example, Journal of Combinatorial Theory, series
A, vol. 18, pp. 336--341, vol. 20, pp. 363--364, vol. 24, pp. 126--127, vol.
26, pp. 82--83, and vol. 27, pp. 365--366.  Also, see Richard K. Guy's
Unsolved Problems in Number Theory, Springer-Verlag, 1981.
--

Professor Edward M. Reingold                  reingold@cs.uiuc.edu
Department of Computer Science                (217) 333-6733
University of Illinois at Urbana-Champaign
1304 W. Springfield Ave.
Urbana, IL 61801-2987  USA