Avoiding Colinear Points

[Richard Guy]

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 at adelphia.net>
>> To: "Leroy Quet" <qq-quet at mindspring.com>
>> Cc: "Leroy Quet" <qq-quet at mindspring.com>; <seqfan at 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).
>