What is a minimum number of $1\times 3$ tiles that can be put on a table $5\times 5$ so that no more tiles $1\times 3$ can be put on it?

Question

What is a minimum number of $1\times 3$ tiles that can be put on a table $5\times 5$ so that no more tiles $1\times 3$ can be put on it?

It is 5 but I can not prove that if we put 4 tiles there is still room for one more. I think there must be some rigor proof using Hall marriage theorem.

Answer 1

You can set $5$ tiles just by placing one on each row. But why is this the minimum (so that you cannot place anymore)? Why is that if you have $4$ tiles there you can always place another one?

Place $4$ tiles in the board.

• If all the tiles are facing in the same direction, we clearly have space for one more (in the same direction).
• If all but one are facing the same direction, let there be three horizontal tiles and a vertical one. Since there are at most two consecutive vertical squares over (or below) the horizontal tiles, the vertical tile must be to the left (or to the right) of some horizontal tile. This means that we can place another horizontal tile over (or below) some horizontal tile.
• If there are two horizontal and one vertical, there are at most $3$ vertical consecutive squares. If the vertical squares are there, this means that we still have space for other three vertical tiles. If the vertical squares are to the left (or to the right) of the horizontal ones, we have space for other $3$ horizontal tiles.

This is much easier to visualize with a few examples than by words. I know you were probably looking for a rigorous proof but unless there is a simple argument, I don't know if it will get much simpler than this.