10
$\begingroup$

You have an 8x8 board, and you must partially cover it with a single kind of tetromino in such a way that it is impossible to place any additional tetrominoes of that kind in the empty spaces. Additionally, no two tetrominoes may touch by their edges.

I consider tetrominoes that are reflections of each other to be different, so there are 7 possible choices:

I, J, L, O, S, T, Z.

For which tetrominoes is this possible, and how many pieces does it require (minimum)?

$\endgroup$
8
$\begingroup$

A partial solution complementary to IanMacDonald's.

It is possible for this pair

S and Z
Place them in a fairly symmetric array, as follows. S is mirror image of Z.
enter image description here Now to prove that the minimal number of pieces is eight!

There is another tile that works:

It's "T" time [again]: enter image description here Again this seems to require eight tilesIt looks like this requires seven tetrominos.


Added proof that it is impossible to get out of "JaiL"

There is a pair of tetrominos that are unable to tile the chessboard.

This is a fairly exhaustive (and exhausting) proof that J tetromino (and by symmetry the L tetromino) cannot tile the board.
The proof starts by showing that tiling is impossible on an infinite board.
Then to avoid this on the chessboard, all pieces must be in close proximity to an edge or corner. The next diagram shows there are three mandatory cells around every piece (blue) - these must be occupied or there will be a vacancy (gray) of the J shape. These are shown in light blue, assuming the playing field is rotated so that piece 1 is oriented as shown. enter image description here Then there are four possible positions of a second piece to cover the mandatory cell on the right. Two of these are shown in the next diagram. Both of these lead to a J vacancy because the second piece introduces new mandatory cells that cannot be occupied simultaneously (the red X's). Neither of these can be moved close to the top edge of a chessboard to avoid vacancies. In the first case, the gray J on the left will then be unavoidable. In the second case, rotational symmetry means the upside-down arrangement is very far from the new top edge. enter image description here Then one other orientation immediately leads to a J vacancy, so there is only one possible orientation of the second piece relative to the first. This applies to a third piece relative to the second, and so on. So the result is a closed figure with an interior that cannot accomodate any more non-touching J pieces, but which has J vacancies. enter image description here In the last case, the cyclic arrangement can be avoided by placing the first two tetrominos against the top edge. But then, one of the next three arrangements results (the case where there is one column to the left is trivial), where placement of all the light blue pieces is forced, resulting in a J vacancy or touching edges in each case. enter image description here
The only other way to avoid one of these arrangements is to place tetromino 1 so that it is abutting the right edge of the chessboard, so that there is no need to place tetromino 2 as in previous arrangements. Then **all tetrominos* must be placed this way with the "top" of the J touching an edge. The resulting arrangement leaves a 2x2 vacancy at the center of the board and hence the four mandatory cells in the next figure. Then J pieces can be placed in one of two symmetric ways (otherwise one of the mandatory cells will be vacant). But then it is impossible not to leave a J vacancy. enter image description here

$\endgroup$
  • $\begingroup$ Very cool! I have a different solution for S/Z and T. I noticed that your S/Z tiling could be expanded upwards +3 tiles at a time, and rightwards +2/+3 tiles at a time thus solving S/Z in the case of boards sized $3n+2$ by $5m$ or $5m-2$. $\endgroup$ – Ben Frankel Sep 13 '15 at 16:38
  • $\begingroup$ Good observation. I am still working on the J/L tilings. $\endgroup$ – Marconius Sep 13 '15 at 17:49
  • $\begingroup$ +1 Yup. That JL is exactly what I found out, I'm just unable to make pretty pictures. :) $\endgroup$ – Ian MacDonald Sep 14 '15 at 20:47
  • $\begingroup$ @IanMacDonald - Thanks. Drawing were done in Excel, using primarily cell background colours and borders, with adjusted row height (24) and column width (4). I am curious whether the S/Z and T tilings are minimal or not - may need to write a computer program for this ;-) $\endgroup$ – Marconius Sep 14 '15 at 21:28
  • $\begingroup$ I'm going to read through your JaiL proof and see if I agree. In the meantime, since it may seem as if the question has been answered in its entirety, I'll let you know that it hasn't. Your T solution is not optimal. $\endgroup$ – Ben Frankel Sep 14 '15 at 21:47
5
$\begingroup$

Partial answer.

It is impossible for

I
Any piece that is placed must have the adjacent sides empty, leaving a shadow that exactly matches its own shape.

It is possible for

O
Place them all one square apart in a lattice.
enter image description here

It is impossible for

J/L.
I'm not good at drawing pretty pictures, but the trouble is that at some point you will have a 3-flat exposed to the inside of the square instead of being able to flush up against the edge. There are too many holes that need to be filled, which always ends up leaving a piece-sized gap.

$\endgroup$
  • $\begingroup$ @Anachor, If you choose X tetromino, you only have to ensure that no more X's can be inserted. (where X is any tetromino) $\endgroup$ – Ben Frankel Sep 13 '15 at 6:12

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.