# Planning an Archipelago

We can place S and Z tetromino shaped islands on an 8x8 grid of water in such a way that no two islands are touching by their edges, because then they would not be two islands. Two islands may touch by their corners.

Do this in a way that minimizes the size of the largest pond in the grid.

• So, you're trying to pack and 8x8 grid with S and Z tetrominoes such that no two are touching on an edge and the largest contiguous unfilled space is minimized?
– Deusovi
Sep 8, 2015 at 0:36
• @Deusovi, Exactly. :) Sep 8, 2015 at 0:41
• Fixed or rotatable? Sep 8, 2015 at 0:44
• @moonbutt74, Rotatable. Sep 8, 2015 at 0:46
• @moonbutt74, Actually yesterday I wrote a program that lets me draw colors on a grid and that's what I used for this puzzle, but I usually use graph paper. Sep 8, 2015 at 2:00

The best I can do so far is 5.

Edit: Got 4!

• Good solution! That's the best I can do as well. Let's see if someone can come up with something better. Sep 8, 2015 at 0:56
• @Ben: Take a look now! :D
– Deusovi
Sep 8, 2015 at 0:58
• Wow. I didn't think 4 would be possible because my solution had 3 ponds of size 5, but seeing your first solution made me think it might be possible. Nice job. I'm reasonably certain that 3 is unattainable but I'll wait before accepting this because I only asked the question 30 minutes ago and I'd like to give more people a chance to try. Sep 8, 2015 at 0:59
• That's the best you can do and it is not hard to prove. Start with a corner 2x2 square, place a tetramino which covers at least one of the 4 1x1 squares and from there on it is pretty straightforward to place the remaining tetraminos without leaving a pond of size 4 until you see that's impossible. Just use the little corner at the bottom of the tetramino - it always has to be covered by another tetramino. Sep 8, 2015 at 1:16
• @ArturKirkoryan, I think I agree that that's the best you can do, but I don't agree that it's not hard to prove. If you have a simple proof then I would like to see it in the form of an answer. Thanks :) Sep 8, 2015 at 2:21

For completeness, decided to add the optimality proof.

Assume the opposite - i.e. you can cover the board with tetraminos, such that there is not a pond of size larger than 3.

Now consider the 4 squares a7, a8, b7, b8. At least one of them should be covered by a tetramino.

Case 1. Only one square is covered. Now there are basically 3 different subcases to consider, first two of which are straightforward:

For the third case, when we have a tetramino on b8, c8, c7, d7, has 2 subcases. The first one leads us to (up to symmetry)

and the second one leads us to

Case 2. 2 squares are covered. WLOS let them be b7 and b8. Now using the observation above it is easy to see that we should have tetraminos on the following 2 places:

However, now the square d6 is an issue and once again we get a contradiction.

Case 3. 3 squares are covered. If a8 is covered, then (up to symmetry) we get:

Otherwise WLOG we have a tetramino on a7, b7, b8, c8. Also because of the observation above the square c6 should be covered as well. Similarly, a2, b1, b2, c3 should be covered by tetraminos. Now it is easy to see that a4, a5, a6, b6 can not be covered by tetraminos, so once again we get an island of size 4. Contradiction.

• Your conclusion in case 1 is wrong. You can have tetrominos on b7-c7-c8-d8 and a6-a5-b5-b4. Sep 8, 2015 at 6:13
• Case 3 needs also way more explanations. For example b5-b4-a4-a3 and c3-c2-b2-b1 are possible. Sep 8, 2015 at 6:25
• The third case works only if you sucessfully ruled out all other cases. You are still missing the main case a8-b8-b7-c7. Sep 8, 2015 at 8:24
• There are even 2 more cases: b8-c8-c7-d7 and then either a7-a6-b6-b5 or a6-b6-b5-c5. Sep 8, 2015 at 8:41
• You are right - you need to rule out the first 2 cases first in order to apply the third one. Added the rest cases/subcases and checked carefully - there aren't others. Thank you for the feedback. Sep 8, 2015 at 15:57