login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 5
0, 1, 2, 4, 8, 12, 17, 23, 30, 39 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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.

LINKS

Table of n, a(n) for n=1..10.

EXAMPLE

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)

CROSSREFS

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.

Sequence in context: A273109 A046843 A292060 * A305694 A176562 A100057

Adjacent sequences:  A152122 A152123 A152124 * A152126 A152127 A152128

KEYWORD

nonn,hard,more

AUTHOR

Joshua Zucker, Mar 25 2009

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 19:34 EDT 2018. Contains 316530 sequences. (Running on oeis4.)