5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Deusovi Sep 8 '15 at 0:36
  • $\begingroup$ @Deusovi, Exactly. :) $\endgroup$ – Ben Frankel Sep 8 '15 at 0:41
  • $\begingroup$ Fixed or rotatable? $\endgroup$ – moonbutt74 Sep 8 '15 at 0:44
  • 1
    $\begingroup$ @moonbutt74, Rotatable. $\endgroup$ – Ben Frankel Sep 8 '15 at 0:46
  • 1
    $\begingroup$ @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. $\endgroup$ – Ben Frankel Sep 8 '15 at 2:00
8
$\begingroup$

The best I can do so far is 5.

board

Edit: Got 4!

board2

$\endgroup$
  • $\begingroup$ Good solution! That's the best I can do as well. Let's see if someone can come up with something better. $\endgroup$ – Ben Frankel Sep 8 '15 at 0:56
  • $\begingroup$ @Ben: Take a look now! :D $\endgroup$ – Deusovi Sep 8 '15 at 0:58
  • $\begingroup$ 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. $\endgroup$ – Ben Frankel Sep 8 '15 at 0:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Puzzle Prime Sep 8 '15 at 1:16
  • 1
    $\begingroup$ @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 :) $\endgroup$ – Ben Frankel Sep 8 '15 at 2:21
4
$\begingroup$

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:

enter image description here enter image description here

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)

enter image description here

and the second one leads us to

enter image description here

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:

enter image description here

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.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Your conclusion in case 1 is wrong. You can have tetrominos on b7-c7-c8-d8 and a6-a5-b5-b4. $\endgroup$ – Sleafar Sep 8 '15 at 6:13
  • 1
    $\begingroup$ Case 3 needs also way more explanations. For example b5-b4-a4-a3 and c3-c2-b2-b1 are possible. $\endgroup$ – Sleafar Sep 8 '15 at 6:25
  • 1
    $\begingroup$ The third case works only if you sucessfully ruled out all other cases. You are still missing the main case a8-b8-b7-c7. $\endgroup$ – Sleafar Sep 8 '15 at 8:24
  • 1
    $\begingroup$ There are even 2 more cases: b8-c8-c7-d7 and then either a7-a6-b6-b5 or a6-b6-b5-c5. $\endgroup$ – Sleafar Sep 8 '15 at 8:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Puzzle Prime Sep 8 '15 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.