|
|
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 no four of the painted ones form a square with sides parallel to the grid.
|
|
16
|
|
|
1, 3, 7, 12, 17, 24, 32, 41, 51, 61, 73, 85, 98
(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.
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
a(12) = 85 and a(13) = 98 were obtained with a MIP model, solved with Gurobi in 141 days on 32 cores. - Simon Felix, Nov 22 2019
|
|
LINKS
|
|
|
EXAMPLE
|
n=9. A maximum of a(9) = 51 points (X) of 81 can be painted 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).
For analogs that avoid triangles in the square grid see A271906, A271907.
For the three-dimensional analog see A268239.
|
|
KEYWORD
|
nonn,hard,nice,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(12)-a(13) from Simon Felix using integer programming, Nov 22 2019
|
|
STATUS
|
approved
|
|
|
|