My question is inspired by this question.
There is a rectangular room of dimension $a \times b$, and there is an unlimited number of rectangular tiles of dimension $c \times d$. You are allowed one cut on each tile, but the cut must be parallel to the edges. So you basically have tiles of dimension $c \times y$ where $y \le d$, and dimension $x \times d$ where $x \le c$.
The question is whether you can tile the room with such tiles. (Note: you are allowed to rotate tiles by $90$ degrees.)
In the original question, $a = 140, b = 370, c = d = 30$ and @achillehui came up with a nice coloring argument (see comment to main post) where the room is colored in a checkerboard pattern of $15 \times 15$ squares. So each (cut or uncut) tile covers equal areas of white and black, while the room can be colored in such a way that it's not half-and-half, thereby proving the tiling is impossible.
My question: AFAICT, the coloring argument depends on $c, d$ both being even multiples of the same number $15$ (which can happen iff $\frac{c}{d}$ is rational). What if this is not the case? E.g. what if $c = 30, d = 10 \pi$? Intuitively it still seems impossible to tile the room, but I cannot generalize the coloring argument (nor come up with a different proof).
What I seek:
-
Ideally, a general criterion for when tiling is possible (as a function of $a,b,c,d$)
- Partial result: note that rotating does help, e.g. if either room side $= m c + n d$ for non-negative integers $m,n$ then tiling is possible (regardless of the other room side). In fact I wouldn't be surprised if this turns out to be the necessary-and-sufficient condition.
-
Failing that, a proof whether my example above (where $a,b,c,d = 140, 370, 30, 10\pi$) can be tiled or not.
-
Failing that, any (non-trivial) result using a different example where $a, b$ are rational and $\frac{c}{d}$ is irrational.
Best Answer
I will use essentially the same as the second proof on this site where it is used to prove
The first proof there is the checkerboard colouring one.
I have changed the second proof slightly to show that in this problem at least one side $a$ or $b$ must be a linear combination of $c$ and $d$.
Proof:
Suppose you have tiled the $a\times b$ rectangle.
Construct a graph where the vertices are the points where corners of the tiles lie, and two vertices are connected if there is a tile with corners at those two vertices and the side between them is of length $c$ or length $d$. Note that if you use an uncut tile, treat it as if it were cut along one of its dimensions. In this way every tile contributes exactly two edges to the graph, incrementing the degree of all four vertices.
The vertices at the corners of the large rectangle have degree 1, but all other vertices have degree 2 or 4 because at each vertex there are either two or four tile corners coming together, because there are exactly two or four 90-degree corners at those points.
You now walk along this graph, starting at one corner of the rectangle. Never use any edge twice. Eventually you will have to end on an odd degree vertex, which must be one of the other corners of the large rectangle.
The start and end vertex lie a distance of $a$ or $b$ apart along one of the axes, but all the steps you took along that same axis were of length $c$ or $d$. Therefore $a$ or $b$ (or even both) must be some linear combination of $c$ and $d$.
This proves that your example of $(a,b,c,d)=(140,370,30,10\pi)$ is not possible.
Note that the linear combination $mc+nd$ might use negative $m$ or $n$. As an example of this, you can take two $c\times (c-d)$ tiles, two $c\times x$ tiles, surrounding one $(c-x)\times d$ tile, to form a $(2c-d)\times(c+x)$ rectangle. (This assumes w.l.o.g. $c\ge d$, and $x$ is any value $x\le d$.)