[seqfan] Re: Destroying lattice squares
Rob Pratt
Rob.Pratt at sas.com
Wed Mar 25 20:54:37 CET 2009
This greedy algorithm is a well-known heuristic for set covering problems. A simple post-processing improvement step is to then try to "unremove" some removed dots while still covering all squares.
I used integer programming to compute the optimal answers for n <= 9:
0,1,2,4,8,12,17,23,30
Also, 35 <= a(10) <= 39.
We also have the upper bound a(n) <= a(n-1) + 2n - 1, by removing the dots along the two new edges.
-----Original Message-----
From: seqfan-bounces at list.seqfan.eu [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Dmitry Kamenetsky
Sent: Wednesday, March 25, 2009 5:08 AM
To: Sequence Fanatics Discussion list; israel at math.ubc.ca; joshua.zucker at gmail.com
Subject: [seqfan] Re: Destroying lattice squares
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/
>
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list