A227116 -id:A227116 - 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

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

A152125 Consider a square grid with side n consisting of n^2 cells (or points); a(n) is the minimal number of points that can be painted black so that, out of any four points forming a square with sides parallel to the sides of the grid, at least one of the four is black.

Original entry on oeis.org

0, 1, 2, 4, 8, 12, 17, 23, 30, 39, 48, 59, 71

Offset: 1

Joshua Zucker, Mar 25 2009

On a 4 X 4 square grid, there are 14 lattice squares parallel to the axes. What is the fewest dots you can remove from the grid such that at least one vertex of each of the 14 squares is removed? The answer is a(4) = 4. In general a(n) is the answer for an n X n grid.
This is a "set covering problem", which can be handled by integer linear programming for small n. - Robert Israel, Mar 25 2009
This sequence is complementary to A227133: A227133(n) + a(n) = n^2.

			1 X 1: 0 dots, since there are already no squares,
2 X 2: 1 dot, any vertex will do,
3 X 3: 2 dots, the center kills all the small squares and you need one corner to kill the big square,
a(4) = 4: there are 4 disjoint squares, so it must be at least 4, and with a little more work you can find a set of 4 dots that work.
From _Robert Israel_: (Start)
For the 5 X 5 case, Maple confirms that the optimal solution is 8 dots,
which can be placed at
[1, 1], [1, 3], [2, 2], [2, 3], [3, 0], [3, 1], [3, 2], [4, 4]
For the 6 X 6 case, Maple tells me that the optimal solution is 12 dots,
which can be placed at
[0, 5], [1, 1], [1, 2], [1, 4], [2, 0], [2, 3], [2, 4], [3, 1], [3, 3],
[4, 0], [4, 4], [5, 2]
For the 7 X 7 case, Maple tells me that the optimal solution is 17 dots,
which can be placed at
[0, 0], [1, 2], [1, 3], [1, 5], [2, 1], [2, 4], [2, 5], [3, 2], [3, 3],
[3, 4], [4, 1], [4, 2], [4, 5], [5, 1], [5, 3], [5, 4], [6, 6]
For n=9, at least a(9) = 30 points (.) have to be removed while 51 (X) of 81 are remaining. The solution is unique (congruent images being ignored).
      . 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 .
(End)

Ed Wynn, A comparison of encodings for cardinality constraints in a SAT solver, arXiv:1810.12975 [cs.LO], 2018.

See A227133 for an equivalent version of this problem.
A227116 treats an analogous question but for equilateral triangles instead of squares.
A000330 gives the number of subsquares in a square grid of side n.
Cf. also A240443.

a(5)-a(7) from Robert Israel, Mar 25 2009
a(8)-a(9) from Heinrich Ludwig, Jul 01 2013
a(10) from Giovanni Resta, Jul 14 2013 (see A152125).
Reworded definition to align this with several similar sequences (A227133, A240443, A227116, etc.). - N. J. A. Sloane, Apr 19 2016
a(11)-a(13) (using A227133) from Alois P. Heinz, May 05 2023

A240114 Maximal number of points that can be placed on a triangular grid of side n so that no three of them are vertices of an equilateral triangle in any orientation.

Original entry on oeis.org

1, 2, 4, 6, 8, 10, 12, 14, 17, 20, 22, 25, 28, 31, 34

Offset: 1

Heinrich Ludwig, Apr 01 2014

Placing points on a triangular grid of side n, there are A000332(n + 3) triangles to be avoided.
The number k(n) of maximal solutions (reflections and rotations not counted) varies greatly: k(n) = 1, 1, 1, 1, 1, 3, 13, 129, 15, 2, 63, 3, 20, 1, ...
From Elijah Beregovsky, Nov 20 2022: (Start)
a(n) >= 3n-11.
This lower bound is given by the construction seen in the example section.
Conjecture: for n >= 11, a(n) = 3n-11. (End)

			On a triangular grid of side 15, 34 points (X) can be placed so that no three of them form an equilateral triangle, regardless of its orientation.
                   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 . .

Cf. A227308, A227116, A227133, A000332.

a(14) from Heinrich Ludwig, Jun 20 2014

a(15) from Heinrich Ludwig, Jun 21 2016

A319158 Given an equilateral triangular grid with side n, containing n(n+1)/2 points, a(n) is the minimal number of points to be selected, such that any equilateral triangle of points will include at least one of the selection, if the triangle has the same orientation as the grid.

Original entry on oeis.org

0, 1, 2, 4, 6, 9, 13, 18, 23, 29, 35, 43, 51

Offset: 1

Ed Wynn, Sep 12 2018

This is the complementary problem to A157795: A157795(n-1) + a(n) = n(n+1)/2.

This is the same problem as A227116, except that here the triangles must have the same orientation as the grid. Here, the triangle's sides must be aligned with the sides of the grid, and the horizontal side of the triangle must be its base (assuming the grid has a horizontal base). A227116 is different in that it also includes upside-down triangles, rotated 180 degrees compared to the grid, since these have sides aligned with the grid (but different orientation).

			For n=5, there is a unique solution for a(5)=6 (representing selected points by O):
        O
       . .
      , O ,
     . O O .
    O . , . O
It can be seen that this is not a valid solution for A227116 because of the upside-down triangle of commas. One solution for A227116(5)=7 would be to select one of the commas as well.

Ed Wynn, A comparison of encodings for cardinality constraints in a SAT solver, arXiv:1810.12975 [cs.LO], 2018.

Cf. A157795, A227116, A319159.

A319159 Given an equilateral triangular grid with side n, containing n(n+1)/2 points, a(n) is the minimal number of points to be selected, such that any equilateral triangle of points will include at least one of the selection.

Original entry on oeis.org

1, 2, 4, 7, 11, 16, 22, 28, 35, 44, 53, 63, 74, 86

Offset: 1

Ed Wynn, Sep 12 2018

This is the complementary problem to A240114: a(n) + A240114(n) = n(n+1)/2.

This is the same problem as A227116 and A319158, except that here the triangles may have any orientation. Due to the additional requirements, a(n) >= A227116(n) >= A319158(n).

			For n=4, this sequence has the same value a(4)=4 as A227116 and A319158, but if we look at the three solutions to those sequences (unique up to symmetry), representing selected points by O:
        O             O             O
       O ,           . ,           . .
      , . O         , O .         . O .
     . O , .       O . , O       . O O .
We see that only the last of these is a solution here -- the others have rotated triangles not including any selected point (for example, as shown with commas).  The last selection is therefore the unique solution (up to symmetry) for a(4)=4.

Ed Wynn, A comparison of encodings for cardinality constraints in a SAT solver, arXiv:1810.12975 [cs.LO], 2018.

Cf. A227116, A240114, A319158.

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

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

A152125 Consider a square grid with side n consisting of n^2 cells (or points); a(n) is the minimal number of points that can be painted black so that, out of any four points forming a square with sides parallel to the sides of the grid, at least one of the four is black.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A240114 Maximal number of points that can be placed on a triangular grid of side n so that no three of them are vertices of an equilateral triangle in any orientation.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A319158 Given an equilateral triangular grid with side n, containing n(n+1)/2 points, a(n) is the minimal number of points to be selected, such that any equilateral triangle of points will include at least one of the selection, if the triangle has the same orientation as the grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A319159 Given an equilateral triangular grid with side n, containing n(n+1)/2 points, a(n) is the minimal number of points to be selected, such that any equilateral triangle of points will include at least one of the selection.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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