[seqfan] Re: Destroying lattice squares

[Robert Israel]

It's a "set covering problem", which can be done by integer linear 
programming for small n.
For the 5x5 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 6x6 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 7x7 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]

Cheers,
Robert Israel

On Wed, 25 Mar 2009, Joshua Zucker wrote:

> 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
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>