What is the smallest number of cells you need to paint in an 8x8 grid, such that it contains no unpainted pentominoes? Can you find multiple solutions? Note that a pentomino is a set of 5 adjacent cells (horizontally or vertically).
Good luck!
$\begingroup$
$\endgroup$
asked Oct 13 '19 at 13:03
$\begingroup$
$\endgroup$
Certainly 24 suffices: the c and f files and 3 and 6 ranks, minus their intersections. That leaves 2×2 and 1×1 squares.
But I don't know whether that's the least.
-
$\begingroup$ yes good point. We still need to prove minimality and thank you for your honesty. $\endgroup$ – Dmitry Kamenetsky Oct 13 '19 at 13:29
-
$\begingroup$ There are other solutions that are very different to yours. Are you able to find them? $\endgroup$ – Dmitry Kamenetsky Oct 14 '19 at 0:15
$\begingroup$
$\endgroup$
Here is another solution with the same number of squares as @msh210's:
For 24,
This looks very different to @msh210's, and has the nice property that
All blank regions are tetrominoes
Furthering on from that:
We might try a perimeter argument. Suppose there were 17 filled squares. Since all the blank regions are tetrominoes or smaller, the total perimeter of the blank regions is at least 2 times the number of blank squares. Also, the total perimeter is 4 times the number of filled squares plus all the border edges minus twice the number of border edges adjacent to a black square (at least six). Thus 94=47*2<=total perimeter<=4*17+32-2*6=88, a contradiction. So there are at least 18 filled squares.
-
$\begingroup$ Very nice solution. If all the blanks are tetrominoes, could you somehow use this fact to prove that the solution is indeed optimal? $\endgroup$ – Dmitry Kamenetsky Oct 14 '19 at 0:51
-
3$\begingroup$ I don't think that's enough on its own, because you could trivially come up with solutions where all the blanks are tetrominoes, but it is not optimal (e.g. leave one 2x2 square empty and fill in everything else). I think the real thing to optimize is how many sides of filled squares are "useful" in that they are adjacent to a blank square, rather than being next to another filled square or a border. For example, this solution has 8 non-useful sides on the borders (the corner square has 2) and 16 non-useful sides that are adjacent to each other. $\endgroup$ – hdsdv Oct 14 '19 at 2:03
-
$\begingroup$ @hdsdv If you could formalise that into a solution I’d be very interested to see it! I just added the observation as a very crude lower bound - there’s definitely plenty of room for refinement but I didn’t particularly feel like proof by exhaustion today. $\endgroup$ – boboquack Oct 14 '19 at 8:43
-
$\begingroup$ @DmitryKamenetsky why the checkmark? There's still a long way to go to prove minimality... $\endgroup$ – boboquack Oct 17 '19 at 6:13
-
$\begingroup$ Yes good point. Although I felt convinced... $\endgroup$ – Dmitry Kamenetsky Oct 17 '19 at 9:38
