Minimal covering of a $5 \times 5$ square with $T$ shaped tetrominoes.

Question

The title almost completely describes the problem. So you have a $5 \times5$ square. You have to fit the minimum number of $T$ shaped tetrominoes such that no more $T$ shaped tetrominoes can be fitted into the square. By skimming through all the possible configurations using a computer program I can safely say that the answer is $3$.

What I cannot figure out is a correct purely mathematical proof. I've tried colouring the square and other things. My attempts prove that the number has to be greater than or equal to $2$ but I cannot really get to the $3$.

Any ideas?

Answer 1

This answer is based on Aqua's (now deleted) approach.

In the diagram there are three potential tetrominoes. There is no way to place a tetromino overlapping both red and green, or both blue and green. So if we want to have two tetrominoes overlapping all of these, one of the tetrominoes must overlap red and blue, and the only way to do that is to cover the marked $3\times 1$ rectangle.

But by rotating this picture, the same argument shows that if we have two tetrominoes and can't place another, we must also have a tetromino covering the horizontal $1\times 3$ rectangle which ends on the same square. These tetrominoes can't be the same (they cover too much space) but also can't be different (they overlap).

Answer 2

The LP relaxation of the integer linear programming formulation given here for this independent domination number problem yields objective value $8/3$, so the integer objective value is at least $\lceil 8/3 \rceil = 3$. By the way, the first several minimum values for an $n \times n$ square are: \begin{matrix} n &3 &4 & 5 &6 &7 &8 &9 &10 &11 &12 &13 &14 &15\\ \text{minimum} &1 &2 &3 &4 &6 &7 &9 &12 &14 &16 &20 &22 &25 \end{matrix}