Re no-3-in-line problem: always check the Index to the OEIS! https://oeis.org/wiki/Index_to_OEIS for this it says: no-three-in-line problem: A000769 <http://oeis.org/A000769>* no-three-in-line problem: see also A000755 <http://oeis.org/A000755>, A037185 <http://oeis.org/A037185>, A037186 <http://oeis.org/A037186>, A037187 <http://oeis.org/A037187>, A037188 <http://oeis.org/A037188>, A037189 <http://oeis.org/A037189>, A107355 <http://oeis.org/A107355>, A007402 <http://oeis.org/A007402>, A000938 <http://oeis.org/A000938>, A212807 <http://oeis.org/A212807>, A219760 <http://oeis.org/A219760> 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 1:00 PM, Warren D Smith <warren.wds@gmail.com> 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)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun