18
$\begingroup$

Assume there is a rectangle be combined by finite squares, and the small squares are not of equal size. Also, the lengths of the squares may be irrational.

The question is "Can we know the ratio of the length and width of this rectangle is rational ?"

I guess the answer is "yes!"(by considering many cases). However, I have no idea to prove it.

$\endgroup$
  • $\begingroup$ Are you requiring that no two of the small squares be congruent or just that they aren't all congruent? $\endgroup$ – lulu Dec 19 '18 at 14:44
  • $\begingroup$ The question does not condition that. In fact, they may be all congruent, but this case would be very simple, And my teacher ask me to consider the cases they are not all congruent, and give a proof. $\endgroup$ – user627221 Dec 19 '18 at 14:50
  • 1
    $\begingroup$ I think you can prove by induction that the smallest square can be used as the standard tile and all other squares can be tiled by it, so that you end up with a rectangular grid of same-size squares. $\endgroup$ – Max Freiburghaus Dec 19 '18 at 15:05
  • $\begingroup$ Gut feeling: There is a proof technique similar to Dehn invariants lurking here. $\endgroup$ – Chris Culter Dec 19 '18 at 17:49
  • 1
    $\begingroup$ @ChrisCulter you are right, insofar as this result was originally proved by Max Dehn. :-) $\endgroup$ – Josse van Dobben de Bruyn Dec 19 '18 at 19:49
8
$\begingroup$

The problem is equivlaent to the following statement:

A rectangle with sides 1 and $x$, where $x$ is irrational, cannot be "tiled" by finitely many squares.

It turns out this is a well known problem and the the proof is copied below from the following source:

http://circuit.ucsd.edu/~yhk/ece269-win18/pdfs/matousek.pdf

However I could not find the name of the author.

enter image description here

enter image description here

$\endgroup$
  • $\begingroup$ Since it resides in a folder http://circuit.ucsd.edu/~yhk/ belonging to Young-Han Kim, I do not know if he is the author? $\endgroup$ – Jeppe Stig Nielsen Dec 19 '18 at 20:08
  • 5
    $\begingroup$ Actually, this is from Jiřì Matoušek, Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra (2010), AMS Student Mathematical Library, number 53. A preliminary version of this book can be found on the website of the late professor Matoušek: kam.mff.cuni.cz/~matousek/stml-53-matousek-1.pdf . $\endgroup$ – Josse van Dobben de Bruyn Dec 19 '18 at 20:13
  • $\begingroup$ @JossevanDobbendeBruyn Thanks, the proof is now complete. $\endgroup$ – Oldboy Dec 19 '18 at 22:15
1
$\begingroup$

Indeed, the ratio between length and width must be rational, even if we don't require the squares to be of different size. The first proof of this was given by Max Dehn [Deh03]. A short and elegant proof appears in Proofs from THE BOOK (see [AZ14, Chapter 28]). Furthermore, I worked out a very similar proof in [Dob16], which I intended to be accessible to undergraduate mathematics students at my university. (It is unclear to me who first conceived of this proof; the original proof of Dehn seems to be much more involved.)

A short sketch of the ideas behind this proof: let $s_1,\ldots,s_n$ denote the lengths of the sides of the squares in the tiling, and let $w,h$ denote the width and height of the large rectangle. Furthermore, let $\mathscr{L} \subseteq \mathbb{R}$ be the $\mathbb{Q}$-vector subspace of $\mathbb{R}$ spanned by $s_1,\ldots,s_n$. (In other words: $\mathscr{L}$ is the set of all rational linear combinations of $s_1,\ldots,s_n$.)

The first important observation is this: for an arbitrary $\mathbb{Q}$-vector space $V$ and an arbitrary $\mathbb{Q}$-bilinear map $f : \mathscr{L} \times \mathscr{L} \to V$, one has $$ f(w,h) = \sum_{i=1}^n f(s_i,s_i).\tag{1} $$ Intuitively, this is generalising the idea that the area of the original rectangle is the sum of the areas of the squares in the tiling. Indeed, the usual area function occurs as a special case, if we choose $V = \mathbb{R}$ and $f(x,y) = x\cdot y$. (For a more detailed proof of (1), see [Dob16, Lemma 3.2].)

Now, if $\varphi : \mathscr{L} \to \mathbb{Q}$ is any linear form, we may consider the $\mathbb{Q}$-bilinear map $f_\varphi : \mathscr{L} \times \mathscr{L} \to \mathbb{Q}$ given by $f_\varphi(x,y) = \varphi(x) \cdot \varphi(y)$. By (1), we have $$ \varphi(w)\cdot \varphi(h) = f_\varphi(w,h) = \sum_{i=1}^n f_\varphi(s_i,s_i) = \sum_{i=1}^n \varphi(s_i)^2 \geq 0. $$ In particular, if $\varphi(w) = 0$, then we must have $\varphi(s_1) = \cdots = \varphi(s_n) = 0$, and therefore $\varphi = 0$ (since $\mathscr{L}$ is spanned by $s_1,\ldots,s_n$). From this it is easy to see that $\mathscr{L}^*$, and therefore $\mathscr{L}$, is at most one-dimensional. Clearly we also have $\dim(\mathscr{L}) \geq 1$, since it contains non-zero numbers, so we conclude that $\mathscr{L}$ is one-dimensional.

Since $\mathscr{L}$ contains $s_1,\ldots,s_n$, it also contains $w$ and $h$. It follows that everything in $\mathscr{L}$ is a rational multiple of, say, $w$. In fact, we have proved something stronger: not only the $h$, but also $s_1,\ldots,s_n$ are rational multiples of $w$.

References:

[AZ14]: Martin Aigner, Günter M. Ziegler, Proofs from THE BOOK, Fifth Edition, Springer-Verlag Berlin-Heidelberg, 2014.

[Deh03]: M. Dehn, Über Zerlegung von Rechtecken in Rechtecke, Mathematische Annalen, Vol. 57 (1903), Issue 3, pp. 314-332.

[Dob16]: Josse van Dobben de Bruyn, Tiling a rectangle with squares, notes for the course SPC taught at Leiden University, available here.

$\endgroup$
1
$\begingroup$

For integer $n \ge 1$, let $[n]$ be a short hand for the interval of integers $\{ 1, 2,\ldots, n \}$.

Let $\{ s_1, s_2, \ldots, s_p \}$ be the set of sides of a bunch of squares that cover a rectangle of dimension $w \times h$.

Since $\mathbb{R}$ is a vector space over $\mathbb{Q}$, there is a hamel basis $E$ of $\mathbb{R}$ over $\mathbb{Q}$. Every real number can be uniquely expressed as a finite linear combination of elements from $E$ with rational coefficients. There will be finitely many of $e \in E$ that appear in the expansion of $s_1, \ldots, s_p$. Let $e_1, \ldots, e_q \in E$ be those appear in expansion of some $s_i$. There will be $p \times q$ coefficients $\alpha_{ij} \in \mathbb{Q}, (i,j) \in [p] \times [q]$ such that

$$s_i = \sum_{j=1}^q \alpha_{ij} e_j\quad\text{ for } i \in [p]$$

Furthermore, for each $j \in [q]$, there is some $i \in [p]$ with $\alpha_{ij}\ne 0$.

Rescale $e_i$ if necessary, we can assume all $\alpha_{ij} \in \mathbb{Z}$.

Under this setting, it is easy to see we can find integers $w_j, h_j \in \mathbb{Z}, j \in [q]$ such that

$$w = \sum_{j=1}^q w_j e_j\quad\text{ and }\quad h = \sum_{j=1}^q h_j e_j$$ For any $j \in [q]$, define function $f_j : [0,w] \times [ 0, h ] \to \mathbb{R}$ by $f_j(x,y) = \frac{\alpha_{ij}}{s_i}$ whenever $(x,y)$ is covered by a square of side $s_i$. Aside from a set of measure zero, $f_j$ is well defined. It is a piecewise constant function and integrable over $[0,w]\times[0,h]$. We can evaluate their integral over $[0,w]\times [0,h]$ in two different orders.

Aside from a finite choice of $y_0$, the line $y = y_0$ cut through finitely many squares "normally". Let $s_{i_1}, s_{i_2}, \ldots, s_{i_r}$ be the sides of the squares it cut through. We have

$$\int_0^w f_j(x,y_0) dx = \sum_{k=1}^r \int_{\sum_{\ell=1}^{k-1} s_{i_\ell}}^{\sum_{\ell=1}^{k} s_{i_\ell}}\frac{\alpha_{i_\ell j}}{s_{i_\ell}} dx = \sum_{k=1}^r \alpha_{i_\ell j} \in \mathbb{Z} $$ Notice $$\sum_{j=1}^q e_j \int_0^w f_j(x,y_0) dx = \int_0^w \sum_{j=1}^q e_j f_j(x,y_0) dx = \int_0^w dx = w$$ We obtain

$$\sum_{j=1}^q \left(\sum_{k=1}^r \alpha_{i_\ell j}\right)e_j = w = \sum_{j=1}^q w_j e_j$$

Since $e_j$ are linear independent over $\mathbb{Q}$, we obtain

$$\int_0^w f_j(x,y_0) dx = \sum_{k=1}^r \alpha_{i_\ell j} = w_j$$

From this, we can deduce $$\int_0^h\int_0^w f_j(x,y) dx dy = w_j h$$

By a similar argument, we have

$$\int_0^w\int_0^h f_j(x,y) dy dx = h_j w$$

Since these functions are integrable, we have

$$w_j h = \int_0^h\int_0^w f_j(x,y) dx dy = \int_0^w\int_0^h f_j(x,y) dy dx = h_j w$$

Since $w \ne 0$, some $w_j \ne 0$. Let's say $w_1 \ne 0$, we have $w_1 h = h_1 w \implies h_1 \ne 0$. As a result, $$\frac{w}{h} = \frac{w_1}{h_1} \in \mathbb{Q}$$

$\endgroup$

Your Answer

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