Welcome to NRICH.

 
A Combinatorial Problem (covering a grid with tiles)
By Anonymous on Friday, September 1, 2000 - 03:35 pm:

I've been pondering a problem that was put to me and I am only a part of the way to discovering a strategy for the problem. Here it is:
You have a 6 by 6 square grid and 18 2 by 1 plates to cover it with. If you cover it and there is a straight line ( made by the perimeter of various plates ) that starts at one end of the grid and ends at the opposite end, the grid has a fault line. Can the grid be covered faultlessly? (ie: with no fault lines )

By Andrew Smith (P2517) on Sunday, September 3, 2000 - 05:13 pm:

If you imagine splitting the grid into two rectangles, 6 by n units and 6 by (6-n) units, it is obvious that to avoid their common edge being a fault line there must be at least one 2 by 1 tile which crosses the edge. Consider now the 6 by n rectangle, one of the squares has already been filled so there are an odd number left, this means there must be at least one other tile which crosses the common edge. This shows that at least two tiles must cross each potential fault line. As there are five potential fault lines running horizontally and five vertically we need at least 20 tiles to avoid a fault line but we can obviously only fit 18 tiles into the grid. Therefore there must always be a fault line.

I first saw this problem about 9 months ago and couldn't do it. When you wrote this I spent about an hour checking all the possibilities by considering how to fill up one edge (from which you're forced into placing lots of others) and it was only when I stopped working on it that the above method struck me. It's one of those problems which has an easy solution but is very difficult to see. Another (which you may have seen) is consider a five by five grid with a person living in each cell, they each think that their neighbours all have better houses than them so all wish to move to a neighbouring cell. Is it possible for them to all move to a neighbouring square (horizontally or vertically but not diagonally)? There is an hard to find step which makes this problem pretty easy but without which it is difficult.