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

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

A240439 Triangle T(n, k) = Numbers of ways to place k points on a triangular grid of side n so that no three of them are vertices of an equilateral triangle of any orientation. Triangle read by rows.

Original entry on oeis.org

1, 1, 1, 3, 3, 1, 6, 15, 15, 3, 1, 10, 45, 105, 114, 39, 3, 1, 15, 105, 420, 969, 1194, 654, 102, 3, 1, 21, 210, 1260, 4773, 11259, 15615, 11412, 3663, 342, 15, 1, 28, 378, 3150, 17415, 64776, 159528, 250233, 234609, 119259, 28395, 2613, 69, 1, 36, 630, 6930

Offset: 1

Heinrich Ludwig, Apr 05 2014

The triangle T(n, k) is irregularly shaped: 0 <= k <= A240114(n). First row corresponds to n = 1.

The maximal number of points that can be placed on a triangular grid of side n so that no three of them form an equilateral triangle is given by A240114(n).

			The triangle begins:
  1,  1;
  1,  3,   3;
  1,  6,  15,   15,    3;
  1, 10,  45,  105,  114,    39,     3;
  1, 15, 105,  420,  969,  1194,   654,   102,    3;
  1, 21, 210, 1260, 4773, 11259, 15615, 11412, 3663, 342, 15;
There are T(5, 8) = 3 ways to place 8 points (x) on a triangular grid of side 5 under the conditions mentioned above:
          .                x                x
         x x              x .              . x
        x . x            x . .            . . x
       x . . x          x . . .          . . . x
      x . . . x        . x x x x        x x x x .

Heinrich Ludwig, Table of n, a(n) for n = 1..138

Cf. A240114, A240443, A084546,
column 2 is A000217,
column 3 is A050534,
column 4 is A240440,
column 5 is A240441,
column 6 is A240442.

A240444 Triangle T(n, k) = Number of ways to arrange k indistinguishable points on an n X n square grid so that no four of them are vertices of a square of any orientation.

Original entry on oeis.org

1, 1, 1, 4, 6, 4, 1, 9, 36, 84, 120, 96, 32, 1, 16, 120, 560, 1800, 4128, 6726, 7492, 5238, 1924, 232, 1, 25, 300, 2300, 12600, 52080, 166702, 416622, 808488, 1196196, 1306464, 1001364, 497940, 141336, 18208, 636, 1, 36, 630, 7140, 58800, 373632, 1895938, 7835492

Offset: 1

Heinrich Ludwig, May 07 2014

The triangle is irregularly shaped: 0 <= k <= A240443(n). The first row corresponds to n = 1.

The maximal number of points that can be placed on an n X n square grid so that no four points are vertices of a square is A240443(n).

			The triangle begins:
  1,  1;
  1,  4,   6,   4;
  1,  9,  36,  84,  120,   96,   32;
  1, 16, 120, 560, 1800, 4128, 6726, 7492, 5238, 1924, 232;
...

Heinrich Ludwig, Table of n, a(n) for n = 1..101

Cf. A240443, A000290 (column 2), A083374 (column 3), A178208 (column 4), A006857 (column 5 divided by 120), A240445 (column 6), A240446 (column 7).

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

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

A240439 Triangle T(n, k) = Numbers of ways to place k points on a triangular grid of side n so that no three of them are vertices of an equilateral triangle of any orientation. Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A240444 Triangle T(n, k) = Number of ways to arrange k indistinguishable points on an n X n square grid so that no four of them are vertices of a square of any orientation.

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