1
$\begingroup$

If a rectangle R can be covered by non-overlapping rectangular tiles, each of which has at least one side with integer length, is it true that R must also have a side with integer length?

$\endgroup$
1
$\begingroup$

Here is a tricky proof (I don't remember where I found it a few years ago ...) :

Consider an orthonormal system and a rectangle K whose sides are parallel to the axes and let :

$$A(K)=\iint_Ke^{2i\pi(x+y)}\,dx\,dy$$

The condition that at least one side of K has integer length is equivalent to $A(K)=0$.

Now, if we suppose that $R$ is tiled by such rectangles, we get $A(R)=0$ as a sum of integrals that are all zero.

$\endgroup$
0
$\begingroup$

Here's a cute proof for which I'll only give hints. Suppose you have such a tiling of the big rectangle:

Colour all integer edges of tiles red (if any of our tiles have all four integer edges, choose two opposite edges and leave the other two uncoloured for simplicity). We now need to show that there exists a red path which begins from one edge of the large rectangle and ends at the opposite edge. Why does the existence of such a path prove the result?

Why would it be even better if we start at one corner and end up at another corner?

For every vertex that meets a red edge, what are the possibilities for how many red edges are touching that vertex? (consider the case that the vertex is a corner of the large rectangle or it is not - if it is not, what are the possibilities?).

Given this, if we start at a corner of the large rectangle and start moving along red edges, and we never take any edge more than once then, first, why can we always keep moving along this path in such a way and, second, why will we always end up at a corner?

$\endgroup$
0
$\begingroup$

Here's another proof using a standard checkerboard method. Overlay a checkerboard pattern onto the large rectangle such that each black and white square has side-length $1/2$ and in such a way that a black square is aligned with the top-left corner of the large rectangle. Let us suppose that the large rectangle does not have an integer-lengthed side, so that the checkerboard necessarily has more black area than white area (why does this happen if and only if we assume the large rectangle does not have an integer-lengthed side?)

Now, every tile of our rectangle has an edge of integer length, so what proportion of each tile is coloured black and what proportion is coloured white?

If we add up the black and white areas of our large rectangle by the areas covered by tiles, what does this tell us? Why does this mean our large rectangle must have an integer-lengthed side?

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