Show that a 6x6 square tiled with dominoes will always have at least one fault line.

All possible fault lines (of which there are 10, 5 horizontal and 5 vertical) split the square into two parts each of which of an even number of squares. 

There must then be an even number of dominoes across any possible fault line to cover the square.

If there are no fault lines then there must be at least one domino across each possible fault line, meaning there must be at least two dominoes across each fault line (evenness).  These domino does not cross any other fault lines.

Thus, if there are no fault lines there must be at least 20 dominoes covering at least 40 squares.  6x6=36 so there are not enough squares to fit the needed dominoes.

Posted by Joel on 2007-03-23 03:26:26