[seqfan] Destroying lattice squares

[Joshua Zucker]

Hi folks,
On the 2009 Bay Area Mathematical Olympiad last month, we asked the
question (paraphrased a bit here):

On a 4x4 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 4, which is easy to see (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).

But we were originally going to ask the same question about a 6x6
grid, but when none of us could solve it, we gave up.  (Apparently the
similar problem for an equilateral triangular grid is well-known and
much easier to solve.)

After a few hours more work, I *still* can't solve the 6x6 question.

I'd love to have a sequence, fewest dots deleted to destroy all the
squares, but all I know is:
1x1: 0 dots, since there are already no squares,
2x2: 1 dot, any vertex will do,
3x3: 2 dots, the center kills all the small squares and you need one
corner to kill the big square,
4x4: 4 dots
5x5: at least 6 dots are needed, with a fairly easy counting proof,
but the best construction I have uses 8 dots.
beyond that I know even less.

Searching for 0,1,2,4 obviously won't get me very far in OEIS!  I
could write a computer program to exhaustively try all the 6 and 7 dot
configurations and get one more term.  Maybe a program is still
realistic for 6x6 as well?

In n dimensions, destroying all the n-cubes, the answers for 1^n, 2^n,
3^n are the same as in the plane.  Beyond that I don't know anything
there, either.

Does anyone have some useful pointers, suggestions for further
research, a clue about someone who has already solved this problem?

Thanks,
--Joshua Zucker