[math-fun] No 3 in line (classic problem by H.Dudeney in early 1900s)
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)
There are many related sequences in OEIS: https://oeis.org/ try author:Hardin (33890 results) or better no three in line (123 results)
Вторник, 10 мая 2016, 20:00 +03:00 от Warren D Smith <warren.wds@gmail.com>:
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
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
Flammenkamp's work on the no-3-in-line problem is summarized in this table: http://wwwhomes.uni-bielefeld.de/achim/no3in/table.txt The only known examples of a fully-symmetric (8 symmetries) set of 2N points on NxN grid, no 3 in line, have (says Flammenkamp) N=2, N=4, and N=10 and each is unique. The N=2 set is, of course, the full 2x2 grid. The N=4 set is the "o"s pictured below: xoox oxxo oxxo xoox and can be regarded as the (x,y) with x*y mod 5=+-2, using the grid with coordinates {1,2,3,4}. I discovered the N=10 set has a nice description: It is the set of (x,y) with x*y mod 11 = +-5. In case you are hoping you can substitute other values for 5 and 11 to get more lovelies, well, I already tried that. Nothing for a long way. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
participants (3)
-
Neil Sloane -
Warren D Smith -
Zak Seidov