This site is supported by donations to The OEIS Foundation.

 Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS"). Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A219760 Martin Gardner's minimal no-3-in-a-line problem. 5
 1, 4, 4, 4, 6, 6, 8, 9, 10, 10, 12, 12, 14, 15, 16, 17, 18, 18, 20, 21, 22, 23, 24, 25, 26, 26, 28 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS a(n) is the minimal number of counters that can be placed on an n X n chessboard, no three in a line, such that adding one more counter on any vacant square will produce three in a line. From Rob Pratt, Mar 29 2014: (Start) Can be computed by using integer linear programming (ILP) as follows. The ILP formulation uses two sets of binary decision variables: x[i,j] = 1 if a queen appears in square (i,j), 0 otherwise y[k] = 1 if line k contains exactly two queens, 0 otherwise Let SQUARES[k] be the set of squares that appear in line k, and let LINES[i,j] be the set of lines that contain square (i,j), so that (i,j) is in SQUARES[k] iff k is in LINES[i,j].  Then we have the following constraints: 2 y[k] <= sum {(i,j) in SQUARES[k]} x[i,j] <= 2 for all lines k [no 3-in-a-line, and if y[k] = 1 then exactly two queens appear in line k] x[i,j] + sum {k in LINES[i,j]} y[k] >= 1 for all squares (i,j) [either a queen appears in square (i,j) or some line that contains square (i,j) contains exactly two queens] The objective is to minimize the sum of all x[i,j]. (End) From Don Knuth, Aug 26 2014: (Start) a(26)=26: there is a solution in which every queen appears in an odd-numbered row and an odd-numbered column, and furthermore cell (i,j) is occupied if and only if cell (j,i) is occupied. Such solutions exist when n=10, 18, 26. Conversely it's known that a(n)>=n when n is even. There are many ways to place n+1 queens that satisfy the conditions, with queens occupying only "white" squares (if the top left corner square is white), at least for n<=30. (End) This is for the "queens" version of the problem, where "lines" are vertical, horizontal and diagonal only.  The version where lines can have any slope is A277433. - Robert Israel, Oct 26 2016 LINKS Alec S. Cooper, Oleg Pikhurko, John R. Schmitt and Gregory S. Warrington, Martin Gardner's minimum no-3-in-a-line problem, Amer. Math. Monthly, 121 (2014), 213-221 (on JSTOR), DOI: 10.4169/amer.math.monthly.121.03.213. Also arXiv:1206.5350 [math.CO]. Gregory S. Warrington, Illustration for n=8 CROSSREFS Cf. A000769, A277433. Sequence in context: A116446 A102126 A277433 * A097918 A256416 A256417 Adjacent sequences:  A219757 A219758 A219759 * A219761 A219762 A219763 KEYWORD nonn,hard,more AUTHOR N. J. A. Sloane, Nov 29 2012 EXTENSIONS Terms a(13)-a(18) from Rob Pratt, Mar 29 2014 Terms a(19)-a(27) from Rob Pratt, Sep 05 2014 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 13 18:07 EST 2018. Contains 318086 sequences. (Running on oeis4.)