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.

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

Offset: 1

Author

Ed Wynn, Jun 09 2017

Keywords

• nonn
• hard
• more

Comments

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

Examples

			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 .
  . . .
		

Crossrefs

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

The number of squares to be considered is A002415.

Formula

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

Extensions

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