This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A152125 #33 May 05 2023 09:06:43 %S A152125 0,1,2,4,8,12,17,23,30,39,48,59,71 %N 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. %C A152125 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. %C A152125 This is a "set covering problem", which can be handled by integer linear programming for small n. - _Robert Israel_, Mar 25 2009 %C A152125 This sequence is complementary to A227133: A227133(n) + a(n) = n^2. %H A152125 Ed Wynn, <a href="https://arxiv.org/abs/1810.12975">A comparison of encodings for cardinality constraints in a SAT solver</a>, arXiv:1810.12975 [cs.LO], 2018. %e A152125 1 X 1: 0 dots, since there are already no squares, %e A152125 2 X 2: 1 dot, any vertex will do, %e A152125 3 X 3: 2 dots, the center kills all the small squares and you need one corner to kill the big square, %e A152125 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. %e A152125 From _Robert Israel_: (Start) %e A152125 For the 5 X 5 case, Maple confirms that the optimal solution is 8 dots, %e A152125 which can be placed at %e A152125 [1, 1], [1, 3], [2, 2], [2, 3], [3, 0], [3, 1], [3, 2], [4, 4] %e A152125 For the 6 X 6 case, Maple tells me that the optimal solution is 12 dots, %e A152125 which can be placed at %e A152125 [0, 5], [1, 1], [1, 2], [1, 4], [2, 0], [2, 3], [2, 4], [3, 1], [3, 3], %e A152125 [4, 0], [4, 4], [5, 2] %e A152125 For the 7 X 7 case, Maple tells me that the optimal solution is 17 dots, %e A152125 which can be placed at %e A152125 [0, 0], [1, 2], [1, 3], [1, 5], [2, 1], [2, 4], [2, 5], [3, 2], [3, 3], %e A152125 [3, 4], [4, 1], [4, 2], [4, 5], [5, 1], [5, 3], [5, 4], [6, 6] %e A152125 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). %e A152125 . X X X X X . X . %e A152125 X . X . . X X X X %e A152125 X X . . X . X . X %e A152125 X . . X X X X . . %e A152125 X X X . X . . X X %e A152125 X . X X X . . . X %e A152125 . X X . . X X . X %e A152125 X X . X . X . X X %e A152125 . X X X X X X X . %e A152125 (End) %Y A152125 See A227133 for an equivalent version of this problem. %Y A152125 A227116 treats an analogous question but for equilateral triangles instead of squares. %Y A152125 A000330 gives the number of subsquares in a square grid of side n. %Y A152125 Cf. also A240443. %K A152125 nonn,hard,more %O A152125 1,3 %A A152125 _Joshua Zucker_, Mar 25 2009 %E A152125 a(5)-a(7) from _Robert Israel_, Mar 25 2009 %E A152125 a(8)-a(9) from _Heinrich Ludwig_, Jul 01 2013 %E A152125 a(10) from _Giovanni Resta_, Jul 14 2013 (see A152125). %E A152125 Reworded definition to align this with several similar sequences (A227133, A240443, A227116, etc.). - _N. J. A. Sloane_, Apr 19 2016 %E A152125 a(11)-a(13) (using A227133) from _Alois P. Heinz_, May 05 2023