A152125 -id:A152125 - cp's OEIS frontend

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.

1, 3, 7, 12, 17, 24, 32, 41, 51, 61, 73, 85, 98

Offset: 1

Heinrich Ludwig, Jul 06 2013

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
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
a(17) >= 158, a(18) >= 174, a(19) >= 192, a(20) >= 210. These lower bounds were obtained using simulated annealing. - Dmitry Kamenetsky, Dec 07 2024

			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.

Dmitry Kamenetsky, Best known solutions for n = 17..20
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)

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.

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 *)

a(10) from Giovanni Resta, Jul 14 2013
a(11) from Paul Tabatabai using integer programming, Sep 25 2018
a(12)-a(13) from Simon Felix using integer programming, Nov 22 2019

A227116 Given an equilateral triangular grid with side n, containing n(n+1)/2 points, a(n) is the minimal number of points to be removed from the grid, so that, if 3 of the remaining points are chosen, they do not form an equilateral triangle with sides parallel to the grid.

Original entry on oeis.org

0, 1, 2, 4, 7, 9, 14, 18, 23, 29, 36, 44, 52, 61, 71

Offset: 1

Heinrich Ludwig, Jul 01 2013

This is the complementary problem to A227308.

Numbers found by an exhaustive computational search for all solutions (see history).

			n = 11: at least a(11) = 36 points (.) out of the 66 have to be removed, leaving 30 (X) behind:
              .
             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 .
There is no equilateral subtriangle with all vertices = X and sides parallel to the whole triangle.

Heinrich Ludwig, Illustration of a(2)..a(15)
Ed Wynn, A comparison of encodings for cardinality constraints in a SAT solver, arXiv:1810.12975 [cs.LO], 2018.

Cf. A227308, A152125, A227133

a(n) + A227308(n) = n(n+1)/2.

Added a(12), a(13), Heinrich Ludwig, Sep 02 2013
Added a(14), Giovanni Resta, Sep 19 2013
a(15) from Heinrich Ludwig, Oct 27 2013

A227308 Given an equilateral triangular grid with side n consisting of n(n+1)/2 points, a(n) is the maximum number of points that can be painted so that, if any 3 of the painted ones are chosen, they do not form an equilateral triangle with sides parallel to the grid.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 14, 18, 22, 26, 30, 34, 39, 44, 49

Offset: 1

Heinrich Ludwig, Jul 06 2013

Numbers found by an exhaustive computational search for all solutions. This sequence is complementary to A227116: A227116(n) + A227308(n) = n(n+1)/2.

Up to n=12 there is always a symmetric maximal solution. For n=13 and n=15 symmetric solutions contain at most a(n)-1 painted points. - Heinrich Ludwig, Oct 26 2013

			n = 11. At most a(11) = 30 points (X) of 66 can be painted, while 36 (.) must remain unpainted.
                .
               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 .
In this pattern there is no equilateral subtriangle with all vertices = X and sides parallel to the whole triangle.

Heinrich Ludwig, Illustration of a(2)..a(15)
Giovanni Resta, Illustration of a(3)-a(14)

Cf. A227116 (the complementary problem), A152125, A227133, A002717.

ivar[r_, c_] := r*(r-1)/2 + c; a[n_] := Block[{m, qq, nv = n*(n+1)/2, ne}, qq = Union[ Flatten[Table[{ivar[r, c], ivar[r-j, c], ivar[r, c+j]}, {r, 2, n}, {c, r - 1}, {j, Min[r - 1, r - c]}], 2], Flatten[Table[{ivar[r, c], ivar[r + j, c], ivar[r, c - j]}, {r, 2, n}, {c, 2, r}, {j, Min[c - 1, n - r]}], 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[{2, -1}, {ne}], Table[{0, 1}, {nv}], Integers]]; Array[a, 9] (* Giovanni Resta, Sep 19 2013 *)

a(12), a(13) from Heinrich Ludwig, Sep 02 2013
a(14) from Giovanni Resta, Sep 19 2013
a(15) from Heinrich Ludwig, Oct 26 2013

A350296 Minimum number of 1's in an n X n binary matrix with no zero 2 X 2 submatrix.

Original entry on oeis.org

0, 1, 3, 7, 13, 20, 28, 40, 52, 66, 82, 99, 117, 140, 164, 189, 215, 243, 273, 304, 336, 376, 414, 454

Offset: 1

Andrew Howroyd, Dec 23 2021

			Solutions for a(3)=3, a(4)=7, a(5)=13, a(6)=20:
  . . 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

Column 2 of A339635.

Cf. A001197, A072567, A152125, A227133, A347472.

a(n) = A347472(n) + 1 = n^2 - A001197(n) + 1 = n^2 - A072567(n).

a(n) >= A152125(n).

a(22)-a(24) computed from A001197, added by Max Alekseyev, Feb 08 2022

A288425 Minimal number of vertices that must be selected from an n X n square grid so that any square of 4 vertices, regardless of orientation, will include at least one selected vertex.

Original entry on oeis.org

0, 1, 3, 6, 10, 15, 22, 30, 39, 50

Offset: 1

Ed Wynn, Jun 09 2017

See the formula and A240443 to deduce lower bounds here: for example, a(11) <= 63, a(12) <= 77.

			For n = 3, an extra selection is required compared to A152125 (which considers only squares with sides parallel to the grid), because of the angled square consisting of the midpoints of the edges. One solution (with selected points shown as X) is:
  X X .
  . X .
  . . .

Cf. A240443 (the complementary problem), A152125, A227116.

The number of squares to be considered is A002415.

a(n) = n^2 - A240443(n).

a(10) derived from A240443(10) by Hugo van der Sanden, Nov 04 2021

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A227116 Given an equilateral triangular grid with side n, containing n(n+1)/2 points, a(n) is the minimal number of points to be removed from the grid, so that, if 3 of the remaining points are chosen, they do not form an equilateral triangle with sides parallel to the grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A227308 Given an equilateral triangular grid with side n consisting of n(n+1)/2 points, a(n) is the maximum number of points that can be painted so that, if any 3 of the painted ones are chosen, they do not form an equilateral triangle with sides parallel to the grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A350296 Minimum number of 1's in an n X n binary matrix with no zero 2 X 2 submatrix.

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions

A288425 Minimal number of vertices that must be selected from an n X n square grid so that any square of 4 vertices, regardless of orientation, will include at least one selected vertex.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions