Printable View
a) Prove that if a perfect cover has no fault-lines, where m, n are even, then 2n + 2m - 4 <= mn/2.
b)Prove that if a perfect cover has no fault-lines, where m is even and n is odd, then 2n+ (3/2)m - 4 <= mn/2.
Can someone show one of these, so I can get an idea on how to do the other. Thanks
I think you will get a quicker answer if you will first define "perfect cover" and "fault line".
Perfect cover = being able to completely cover a chess boards with dominoes with overlapping any of the dominoes
Fault line = A "fault" in a perfect cover. THis means being able to cut the board in such a way that you don't cut, break, move, etc any of the dominoes
And what are m and n in your original problem statement?
Sorry. We are considering an mxn chessboard. m rows and n columns
Here is a sketch of a proof for a), where m and n are even. (I suppose you have probably seen the beautiful proof of the case m=n=6. This is just a slight generalization.)
Assume that a fault-free tiling exists. Then
1. The area of the board is mn square units, so (1/2)mn dominoes are required to cover it.
2. Can a possible fault line be blocked by a single domino? The answer is no, because the board excluding the domino is split into two regions by the fault line. Again excluding the single domino, the area of each region is an odd integer, and such a region cannot be covered by dominoes. Therefore each possible fault line must be blocked by at least two dominoes.
3. A single domino can block at most one fault line.
4. There are m-1 horizontal fault lines possible and n-1 vertical fault lines possible, for a total of m+n-2 possible fault lines. Combined with 2., we see that at least 2(m+n-2) dominoes are required to block all the possible fault lines.
5. Combining 1. and 4.,
(1/2)mn >= 2(m+n-2).
One of the steps above is incorrect when one of the sides of the rectangle has an odd length. I leave it to you to figure out which step it is and how to revise the proof accordingly.