5
$\begingroup$

There is a rectangular grid of $R$ rows and $C$ columns. $R \times C \bmod 4$ of the cells are painted black, and all other cells are white. In other words, there are at least 0 and at most 3 black cells, and the number of white cells is divisible by 4.

I want to cover the white cells using exactly $\lfloor \frac{R \times C}{4} \rfloor$ nonoverlapping tetrominoes. Assuming that the black cells do not divide the white cells into two or more disconnected regions, is it always possible for every possible position of black cells?

Note: I don't know the answer to this puzzle.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

No, it isn't always possible. Consider this 5-by-3 grid with 3 cells painted black.

enter image description here

The 12 white cells can't be split into 3 tetrominos because the four corner cells must be in different tetrominos -- any pair of corners are too far for a tetromino to span both.

Or, here's a smaller counterexample:

enter image description here

The 3 cells in the left column must belong to different tetrominos, but only 2 fit. This counterexample can be extended in height by adding any even number of rows to the top and/or to the bottom.

Another one that's $n$-by-$3$ for any $n \equiv 1 \bmod 4$. It's easy to see the two upper corners must be in different tetrominos that can't both fit.

enter image description here

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ That's a nice counterexample. I think if the top and bottom black cells are fixed, the third black cell can go anywhere on the three middle rows to form an untileable grid. Now I wonder if they are the only counterexamples.. $\endgroup$
    – Bubbler
    Commented Jun 13 at 8:12
  • 2
    $\begingroup$ I notice that the last one still works if you move the top cell left or right, or if you move one of the lower cells down once. $\endgroup$
    – Deusovi ♦
    Commented Jun 13 at 16:07

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