Problem:
a. A board is tiled with dominos. Prove that we can always divide the board into two rectangles each of which is tiled separately (with no domino crossing the dividing line).
b. Is this true for an board?
Problem:
a. A board is tiled with dominos. Prove that we can always divide the board into two rectangles each of which is tiled separately (with no domino crossing the dividing line).
b. Is this true for an board?
Solution:
a.
We say a domino bridges two columns if half the domino is in each column. We show that for the number of dominoes bridging columns and must be at least and even.
Consider first . There cannot be dominos entirely in column , or it would be separately tiled. So there must be at least one domino bridging columns and . The number must be even, because it must equal the number of squares in column (even) less twice the number of dominoes (entirely) in column .
Now suppose it is true for and consider column . There must be at least one domino bridging columns and , or columns thru would be separately tiled. The number must be even, because it must equal the number of squares in column (even) less the number bridging and (even) less twice the number entirely in the column.
So in total there are at least dominos bridging columns. By the same argument there are at least another bridging rows, but there are only dominoes in total.
b.
No. For example:
1 2 3 3 1 1 2 2 1 2 1 2 2 3 3 1 3 3 1 3 1 2 4 1 1 2 2 3 1 2 4 3 1 3 3 2 2 1 2 3 3 2 1 1 4 1 2 1 3 2 3 2 4 3 3 1 1 1 3 2 1 1 2 2