23 Nov 2011
If small rectangles, each of whose either width or height is integer, compose a big rectangle, then the big one has either integer width or height. Prove that.
This problem is just really really difficult. There are 14 proofs in the paper Fourteen Proofs of a Result About Tiling a Rectangle, and there is another one by Peter Winkler.
Those proofs are incomprehensible but one of them, the chessboard proof.
Let's say we paint a 0.5 x 0.5 square onto those rectangles. We alter color each time we paint it.
For example, 1 x 1, 1.3 x 1, and 1.3 x 1.3 rectangle is painted like this:
The painting is genius. Now we can see that, in 1.3 x 1.3, the area of black and white are not equal because of the extra black on the bottom-right corner.
Another critical point to see is that even if we move the rectangles, 1x1 or 1.3x1, but not the painting, the areas are still equal.
If we paint the big rectangle in this manner, we will find that all the small rectangles has equal areas of black and white.
The reasoning goes that, since all the small rectangles has the equal areas of black and white, the big rectangle must have the equal areas of black and white as well.
Therefore, the big rectangle must have at least 1 integer side.
Painting a 0.5x0.5 square is genius.
We can think of it this way.
If the rectangle has the integer height, then every dx on x-axis is equal.
This is because the height is integer, therefore, within dx, there are height black blocks and height white blocks.
It turns out that any size, that divides 1, of square might work, e.g. 1x1. However, a solution with 1x1 square does not handle the case where a small rectangle is also 1x1.