The rectangle R is covered by a finite number of rectangles R1, ... , Rn such that (1) each Ri is a subset of R, (2) the sides of each Ri are parallel to the sides of R, (3) the rectangles Ri have disjoint interiors, and (4) each Ri has a side of integral length. Show that R has a side of integral length.
Solution
Take one of the vertices of R to be at a lattice point. Now count pairs (v, S), where v is a lattice point, S is a small rectangle and v is a vertex of S. A small rectangle S must either have 2 or 4 vertices which are lattice points, so summing over S, the number of pairs is even. The four vertices of R are each vertices of just one small rectangle, but any other vertex must be a vertex of 2 or 4 small rectangles. So summing over v, the total has the same parity as the number of vertices of R which are lattice points. Hence an even number of vertices of R are lattice points. But at least one is a lattice point, so at least two are lattice points. Hence R has at least one side of integral length.
© John Scholes
jscholes@kalva.demon.co.uk
28 Dec 2002
Last corrected/updated 28 Dec 02