login
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
0, 1, 3, 6, 10, 15, 22, 30, 39, 50
OFFSET
1,3
COMMENTS
See the formula and A240443 to deduce lower bounds here: for example, a(11) <= 63, a(12) <= 77.
FORMULA
a(n) = n^2 - A240443(n).
EXAMPLE
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.
Sequence in context: A173106 A022784 A025736 * A022952 A024918 A117245
KEYWORD
nonn,hard,more
AUTHOR
Ed Wynn, Jun 09 2017
EXTENSIONS
a(10) derived from A240443(10) by Hugo van der Sanden, Nov 04 2021
STATUS
approved