8
$\begingroup$

A rectangle is proper if its width is a whole number, or its height is, or both. Show that if a rectangle can be cut into a finite number of proper rectangles, then that rectangle is itself proper.

As obligatory, I claim that this problem has a clever and unexpected solution. Actually, I know of two totally different such solutions.

$\endgroup$
6
$\begingroup$

There is beautiful article on this problem that summarizes 14 different solution approaches:

Stan Wagon: "Fourteen Proofs of a Result About Tiling a Rectangle"
The American Mathematical Monthly 94, 1987, pp. 601-617

There is one very elegant proof via complex double integrals.My favourite proof is as follows :

Proof via prime numbers (due to Raphael Robinson, University of California at Berkeley)
We claim that for each prime p, either the height or the width of the big reactangle $R$ is within $1/p$ of an integer. It follows that one of these is an integer.
To prove the claim, scale the entire tiling up by a factor of $p$ in each direction, and consider the tiling obtained by replacing all tile-corners $(x, y)$ in the scaled-up tiling by $([x], [y])$. This yields an integer-sided rectangle tiled by integer-sided rectangles, each of which has one side a multiple of $p$. Therefore, the area of the large integer-sided rectangle is a multiple of $p$, whence one of its sides must be a multiple of $p$. Moreover, the dimensions of this rectangle differ from the dimensions of the scaled-up rectangle by less than $1$. It follows that $R$ has a side that differs from an integer by less than $l/p$.

$\endgroup$
  • $\begingroup$ That is awesome -- I hadn't know about that article! $\endgroup$ – xnor Apr 3 '15 at 19:55
5
$\begingroup$

Align the bottom left corner of the big rectangle with a checkerboard whose squares have side 1/2. Let the bottom left corner be black.

Two intuitive lemmas:
If both sides of a rectangle aren't whole, then the black area covered will be greater than white area covered. On the contrary, if the black and white areas are equal, then the rectangle must have an integer side.

Proof: Every small rectangle has at least a integer side, so it covers equal areas of black and white. So, the big rectangle (which is the sum of all small rectangles) must cover equal areas of black and white, thus must have an integer side.

enter image description here

Credits: I've read this evidence somewhere few years ago, I don't remember the author though. After googling a bit, I've found out that Stan Wagon has posted 14 solutions of this problem, incredible!

$\endgroup$
3
$\begingroup$

Tile the plane with squares of side length $\frac12$, colored white and black in checkerboard fashion. Because of the periodicity of the coloring, any proper rectangle with sides parallel to the tiles will have the same white area as black area (they will be balanced). Place the larger rectangle, $R$, so that one of its corners lines up with a corner of a white square. Since all of the subrectangles are proper, therefore balanced, $R$ must be balanced. Now, suppose that $R$ was improper. Let $w,h$ be its width and height, and $w',h'$ be those values rounded down. The rectanlges $[0,w']\times [0,h']$, $[0,w']\times [h',h]$ and $[w',w]\times [0,h']$ are all proper, therefore balanced, which would imply the the remaining rectangle, $[w,w']\times[h,h']$, is balanced as well. However, that last rectangle looks something like this: $\qquad\qquad\qquad\qquad\quad$enter image description here
It is simple enough to verify this is imbalanced, using $(1/2-a)(1/2-b)>0$, a contradiction. Technically, I've only covered the case where $w-w'\ge \frac12$ and $h-h'\ge\frac12$, but the other cases are even easier to check.

Thus, $R$ must be proper.

$\endgroup$
0
$\begingroup$

My humble attempt at a simple logic based solution:

Since when I cut a rectangle into proper rectangles, each of the smaller rectangles will have whole numbered widths and heights.

The total width of the rectangle = sum of all widths of smaller rectangles.

Since all the widths are whole numbers their sum is a whole number.

Therefore the width of the original rectangle is a whole number.

Same logic applies for heights.
Since height and width are whole numbers the rectangle is a proper rectangle.

Apparently this solution has some shortcomings according to the given details of the problem. I will be improving on it.

$\endgroup$
  • 1
    $\begingroup$ No, because either width or height are integers for properness, not necessarily both. $\endgroup$ – Rand al'Thor Apr 3 '15 at 12:43
  • $\begingroup$ I guess that makes sense. Sorry for the mistaken assumption. :| $\endgroup$ – archilius Apr 3 '15 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.