[seqfan] Re: Destroying lattice squares

Dmitry Kamenetsky Dmitry.Kamenetsky at nicta.com.au
Wed Mar 25 10:07:31 CET 2009


I've tried the following greedy approach. Construct the set S of all 
squares on the lattice. At each iteration find a dot that appears in the 
most squares in S. If there are many such dots than choose one randomly, 
remove it and remove the squares that contain it from S. Repeat until S 
is empty. Since this is a randomized algorithm, I ran it for 100 times 
and recorded the minimum result. I could reproduce the results given by 
Robert. Although this won't give you the optimal answer for all n, it 
can give you a reasonable upper bound for large n. Here are the first 17 
terms that I computed:

0,1,2,4,8,12,17,24,32,41,52,63,75,90,106,123,142

Hope this helps,
Dmitry



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





More information about the SeqFan mailing list