Good programming-contest problem: Let F(N) be the max possible number of points you can pick from an NxN grid, such that no 3 lie on a line. Find the best lower bounds you can for F(1), F(2), ..., F(256).
I have a program which appears to be capable of showing F(N)>1.57*N for an infinite set of N, although the 1.57 is just a guess based on looking at its results for various N, and might be deluded. (The fact that 1.57 approximates pi/2 is probably just a coincidence?) My program provably exceeds 1.4999*N for an infinite set of N.
A trivial upper bound is F(N)<=2*N, because if you pick 2*N+1 points, then 3 must lie on some horizontal gridline. This trivial upper bound has actually been attained for N=52 and also most N below 52. That was done by Achim Flammenkamp. Perhaps 2N is also attainable for some N>52, perhaps even an infinite set of N. That is unknown.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
From: Zak Seidov <zakseidov@mail.ru> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] No 3 in line (classic problem by H.Dudeney in early 1900s)
There are many related sequences in OEIS: https://oeis.org/ ?
try author:Hardin? (33890 results) or better no three in line ? (123 results)
--My function F(n) does not appear to be in OEIS. I agree there are some related sequences such as https://oeis.org/A000769 (which appears to grow exponentially) and https://oeis.org/A000938 which incidentally appears to grow like 0.2075 * N^4 * (log2(N)-1.125) accurate to within about 1 percent. Assuming the latter N^4*log(N) behavior is roughly correct, then the following random construction: 1. pick Q points randomly from the NxN grid. 2. the number of collinear triples among them is in expectation about 0.2075 * ( log2(N)-1.125 ) * Q^3 / N^2 3. remove 1 point from each such triple to get a no-3-in-line set. will produce about const*N/sqrt(lnN - 0.78) points, no 3 in line, if you use Q of this same order. This is a poor result, I'm just mentioning it so you know how well repaired-randomness does, and also since this formula is rather more complicated than one might have naively expected. The appearance of square root of logarithm basically means that I do not trust my computer program's output for N<200, as a prediction about behavior for large N.