I got the no-three-in-line problem from Heilbronn over 50 years ago. See F4 in UPINT. In Canad. Math. Bull. 11 (1968) 527--531; MR 39 #129 Guy & Kelly conjecture that, for large n, at most (c + eps)n points can be selected, where 3c^3 = 2pi^2 i.e. c ~ 1.85. Curiously, as recently as last March, Gabor Ellmann pointed out an error in our heuristic reasoning, which, when corrected, gives 3c^2 = pi^2, or c ~ 1.813799. I should send a correction to Canad Math Bull! R. PS. For those with a lot of computer time to spare, there's a lot to be discovered. Apart from a limping odd-even phenomenon, the number of solutions with 2n points appears to grow exponentially at first. Who will be the first to show that this begins to tail off? A000769 in OEIS has 3 more terms than I give in UPINT (perhaps due to Flammenkamp?). Also, OEIS says `Extension: It is known that a(n)=0 for all sufficiently large n.' By whom ??? R. On Thu, 21 Oct 2004, David Wasserman wrote:

Good point. Also, a single n-queens solution can already have 3 or more collinear points.

-*-------- ---*------ -----*---- -------*-- ---------* *--------- --*------- ----*----- ------*--- --------*-

...

There is no solution to the n-queens problem for n=2 or n=3. Besides, superimposing two n-queens solutions does not always yield 2n points. For example, here are two 8-queens solutions and their superposition, which only has 13 distinct points.

--*----- -----*-- -*------ ------*- *------- ---*---- -------* ----*---

--*----- -----*-- -------* -*------ ---*---- *------- ------*- ----*---

Superimposed (13 points):

--*----- -----*-- -*-----* -*----*- *--*---- *--*---- ------** ----*---

----- Original Message ----- From: "Jud McCranie" <j.mccranie@adelphia.net> To: "Leroy Quet" <qq-quet@mindspring.com> Cc: "Leroy Quet" <qq-quet@mindspring.com>; <seqfan@ext.jussieu.fr> Sent: Thursday, October 21, 2004 3:54 PM Subject: Re: Avoiding Colinear Points

...

At 04:44 PM 10/21/2004, Leroy Quet wrote:

...

I describe a sequence and game based on the following idea.

If we have a rectangular grid of n lattice-points by n lattice-points, how many dots can we place at the lattice-points, at most one dot per lattice-point, so that no 3 or more dots are colinear (in any direction)?

I get the sequence: 1, 4, 6, 8, 10,.. And Richard Mathar has extended it: 12, 14, (15 or 16),...

The upper bound on each term is obviously 2n, since we can have at most 2 dots in each row and column.

There is an easy approach to this for nxn. If you superimpose any two different n-queens solutions, you get a solution with no three colinear points. Therefore 2n is always possible (for n > 1).