A big rectangle is composed of smaller non-overlapping rectangles, each having integer width or integer height or both. Prove that the big rectangle enjoys the same property.

Do not remember.

1. Fourteen Proofs of a Result about Tiling a Rectangle by S Wagon, The American Mathematical Monthly, vol. 94, 1987, pp. 601-617. The article won the MAA Writing Award in 1988.
2. Solution by David McKay.
3. Solution by E W Dijkstra.
4. Solution by Ulrich Berger.
5. Solution at cut-the-knot.