A board is divided into squares. Onto this board we place several tiles like the one in the picture
(the tiles can be rotated),
each tile covering two squares. At least how many tiles do we need to place onto the board, so that every uncovered square will be adjacent to at least one covered square? (Two squares are adjacent if they share a common side.)
We can place nine tiles as shown in the first picture. Each uncovered square has at least one covered neighbour.
Now, let us show that this cannot be the case if we use less than nine tiles. Put a tile onto the board and mark all the neighbouring squares. Each row contains at most three squares that are either covered or adjacent to a covered square, and these squares are next to each other with no gaps. The same is true for the columns and also for the diagonals. Let us colour nine squares as shown in the third picture. If it were possible to cover the board as required with at most eight tiles, then one of the eight tiles would have to cover or be adjacent to at least two of the coloured squares. This is not possible.