Rectangle with Integer Side


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.

Previous Puzzle: Flipping Bits in a Matrix

An 8×8 matrix contains zeros and ones. You may repeatedly choose any 3×3 or 4×4 block and flip all bits in the block (that is, convert zeros to ones, and ones to zeros). Can you remove all the ones in the matrix?

A room has 100 boxes labeled 1 thru 100. The names of 100 prisoners have been placed in these boxes by the warden. The prisoners shall visit the room one by one. Each prisoner is allowed to inspect the contents of at most 50 boxes, one after the other and leave the room with no communication with other prisoners. If the prisoner discovers his own name in the boxes he inspects, he is released. The prisoners are allowed to collude before hand and devise a strategy to maximize the chances of releasing each and every prisoner. What is their strategy?

17 Aug 2011
© Copyright 2008—2017, Gurmeet Manku.