login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A227133 Given a square grid with side n consisting of n^2 cells (or points), a(n) is the maximum number of points that can be painted so that, if any four of the painted ones are chosen, they do not form a square with sides parallel to the grid. 15
1, 3, 7, 12, 17, 24, 32, 41, 51, 61, 73 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

a(1) through a(9) were found by an exhaustive computational search for all solutions. This sequence is complementary to A152125: A152125(n) + A227133(n) = n^2.

A064194(n) is a lower bound on a(n) (see the comments in A047999). - N. J. A. Sloane, Jan 18 2016

a(11) >= 71 (by extending the n=10 solution towards the southeast). - N. J. A. Sloane, Feb 12 2016

a(11) >= 73, a(12) >= 85, a(13) >= 98, a(14) >= 112, a(15) >= 127, a(16) >= 142 (see links). These lower bounds were obtained using tabu search and simulated annealing via the Ascension Optimization Framework. - Peter Karpov, Feb 22 2016; corrected Jun 04 2016

Note that n is the number of cells along each edge of the grid. The case n=1 corresponds to a single square cell, n=2 to a 2 X 2 array of four square cells. The standard chessboard is the case n=8. It is easy to get confused and to think of the case n=2 as a 3 X 3 grid of dots (the vertices of the squares in the grid). Don't think like that! - N. J. A. Sloane, Apr 03 2016

LINKS

Table of n, a(n) for n=1..11.

Peter Karpov, InvMem, Item 20 [Link added by N. J. A. Sloane, Feb 24 2016]

Peter Karpov, Ascension Optimization Framework [Link added by N. J. A. Sloane, Feb 24 2016]

Peter Karpov, Best configurations known for n = 11 .. 16

Giovanni Resta, Illustration of a(2)-a(10)

Giovanni Resta, Individual illustration for a(8)

EXAMPLE

n=9. A maximum of a(9) = 51 points (X) of 81 can be painted while while 30 (.) must be left unpainted. The following 9 X 9 square is an example:

     . X X X X X . X .

     X . X . . X X X X

     X X . . X . X . X

     X . . X X X X . .

     X X X . X . . X X

     X . X X X . . . X

     . X X . . X X . X

     X X . X . X . X X

     . X X X X X X X .

Here there is no subsquare with all vertices = X and having sides parallel to the axes.

MATHEMATICA

a[n_] := Block[{m, qq, nv = n^2, ne}, qq = Flatten[1 + Table[n*x + y + {0, s, s*n, s*(n + 1)}, {x, 0, n-2}, {y, 0, n-2}, {s, Min[n-x, n-y] -1}], 2]; ne = Length@qq; m = Table[0, {ne}, {nv}]; Do[m[[i, qq[[i]]]] = 1, {i, ne}]; Total@ Quiet@ LinearProgramming[Table[-1, {nv}], m, Table[{3, -1}, {ne}], Table[{0, 1}, {nv}], Integers]]; Array[a, 8] (* Giovanni Resta, Jul 14 2013 *)

CROSSREFS

Cf. A152125 (the complementary problem), A000330, A240443 (when all squares must be avoided, not just those aligned with the grid).

See also A047999, A064194.

For a lower bound see A269745.

For analogs that avoid triangles in the square grid see A271906, A271907.

For an equilateral triangular grid analog see A227308 (and A227116).

For the three-dimensional analog see A268239.

Sequence in context: A310247 A310248 A298022 * A170883 A198463 A140778

Adjacent sequences:  A227130 A227131 A227132 * A227134 A227135 A227136

KEYWORD

nonn,hard,nice,more

AUTHOR

Heinrich Ludwig, Jul 06 2013

EXTENSIONS

a(10) from Giovanni Resta, Jul 14 2013

a(11) from Paul Tabatabai using integer programming, Sep 25 2018

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 15 18:10 EST 2018. Contains 317240 sequences. (Running on oeis4.)