6
$\begingroup$

The following theorem has many proofs, several of which are highlighted in this document.

Whenever a large rectangle is tiled by rectangles, each of which has at least one integer side - the large rectangle has at least one integer side, too.

The document has a proof using prime numbers and scaling:

Prime numbers (Raphael Robinson, Univ. of California, Berkeley) We claim that for each prime $p$, either the height or width of $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 $1/p$ .

I couldn't figure out why it is necessary to have the condition that $p$ be prime.

$\endgroup$
  • $\begingroup$ What is "lip of an integer"? $\endgroup$ – Hagen von Eitzen Dec 31 '14 at 16:05
  • $\begingroup$ It was supposed to be $1/p$. I didn't proofread the OCR very well. $\endgroup$ – picakhu Dec 31 '14 at 19:12
  • $\begingroup$ As an aside, can I just say that this question is a great one to really get people thinking and applying the knowledge they may have from sporadic parts of mathematics without knowing whether it will work or not. It's a question that you can play with and probably succeed in answering with enough effort. $\endgroup$ – Dan Rust Jan 1 '15 at 4:59
  • $\begingroup$ What is meant by $([x],[y])$? $\endgroup$ – Erel Segal-Halevi Jun 3 '16 at 11:30
5
$\begingroup$

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$.

If $p$ were composite, this conclusion would fail.

$\endgroup$

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.