A board is divided into 16 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.)
Solution
We can place four 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 four 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. The board has four corners. If it were possible to cover the board as required with at most three tiles, then one of the three tiles would have to cover or be adjacent to at least two corners. This is not possible.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.