tiling
Let $n\ge 6$ be an even number. An $n$ by $n$ square is tiled by $2$ by $1$ dominoes. They can be placed horizontally or vertically. Must there exist a fault-line, or a line cutting the rectangle without cutting any domino?
I have no clue how to start with this problem. Any hint would be appreciated!
I enumerated all $1183$ tilings (not considering symmetry, and not necessarily fault-free). Of those only $6$ were fault-free, and these are in two symmetry classes.
What's your third one?
Let's assume the top left square is cut off. You can fill the rest of the top row with horizontal dominoes, and the rest of the left column with vertical dominoes. Divide what remains into $2\times 2$ squares. Since $n$ is odd you will have an even number of them...
Best Answer
There is a nice bit of arithmetic for the case $n=6$.
There are 10 possible fault lines, each of which must cut an even number of dominoes.
There are 36 squares and so there are 18 dominoes, each of which cuts precisely one possible fault line.
Therefore one possible fault line cuts no dominoes i.e. it actually is a fault line.
As $n$ increases, the number of dominoes increases much faster than the number of lines and so you can arrange for dominoes to cut each possible fault line.