There is now a new entry in the OEIS for this problem: A272651. Updates welcomed. Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Tue, May 10, 2016 at 4:06 PM, rkg <rkg@ucalgary.ca> wrote:
On searching for 1, 4, 6, 8, 10, 12, 14, 16, 18, ... I got 4 hits, A103517, A175074, A175246, A210939. None of these (as far as we know?) gives the answer to the question, `what is the maximum number of points that can be picked from an n by n grid with no 3 in line?' Forty-odd terms are known from Flammenkamp's work. R.
On Tue, 10 May 2016, Warren D Smith wrote:
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:
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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun