3
$\begingroup$

I recently came across this question: One rectangle, indivisible

The goal is, by tiling 2x1 rectangles, to create a larger rectangle that cannot be split into 2 smaller rectangles.

But my question is this: if using m x n rectangles, when is it impossible to create such a tiling?

Obviously this is impossible for squares, but what else?

$\endgroup$
4
  • $\begingroup$ Welcome to Puzzling! What do you mean by "when is it impossible to create such a tiling"? For what values of m and n? For what size of the larger rectangle? Some combination? This question needs some more constraints on answers. $\endgroup$
    – bobble
    Dec 23 '20 at 23:02
  • $\begingroup$ @bobble I think OP meant to ask "For which values of m and n does an mxn board permit an indivisible domino tiling?" $\endgroup$
    – Bubbler
    Dec 23 '20 at 23:43
  • $\begingroup$ @Bubbler I interpret it to mean: If we use tiles of size mxn (instead of dominos) could it be impossible to make any fault-free rectangle with more than one tile? $\endgroup$ Dec 24 '20 at 0:01
  • $\begingroup$ @JaapScherphuis That makes more sense, given that "obviously this is impossible for squares". $\endgroup$
    – Bubbler
    Dec 24 '20 at 0:11
4
$\begingroup$

Using Jaap's interpretation of the problem, I believe

all non-square tiles can form a rectangle without fault lines.

First claim:

All $1×n$ tiles can form a larger rectangle without fault lines.

Proof by example:

We can extend Roland's $5×6$ pattern for dominoes, so that some pieces are extended to $1×n$ tiles and some others to $(n-1)×n$ tiles:



We can see that the marked $1×n$ tiles are enough to block all possible fault lines, and therefore it does not have any fault lines even if all $(n-1)×n$ tiles are divided into $1×n$ tiles.

Second claim:

All $m×n$ tiles (where $m≠n$), i.e. all non-square tiles, can form a larger rectangle without fault lines.

Informal proof (might have a flaw):

Without loss of generality, assume $m>n$. Put together some tiles side-by-side so that they form a $kn×n$ tile for the smallest possible integer $k$ (which is $\frac{\operatorname{lcm}(m,n)}{n}=\frac{m}{\gcd(m,n)}$). Since $m>n$, we know that $k>1$, so we can "shrink" the $kn×n$ tiles into $k×1$ tiles and form the rectangle shown above. Now, the shrunk $k×1$ piece has some seams at non-integer offsets, namely $\frac{mi}{n}, 0<i<\frac{kn}{m}=\frac{n}{\gcd(m,n)}$, so we need to prove that such seams do not form a fault line across the entire rectangle.

Since $m>n$, we can observe that there is no seam passing through the squares at both ends of the $k×1$ tile. So the shaded cells in the above tiling are seam-free and therefore no fault line can pass through them:



This blocks off all horizontal ($3k$ rows) and more than half of vertical lines ($k+3$ columns). (Remember that the diagrams represent $3k×(2k+1)$ rectangles.) Now it remains to show that the left section does not allow any vertical fault lines.

A lemma is needed at this point:

If two $k×1$ tiles are placed horizontally with 1 horizontal offset, there is no vertical fault line passing the two tiles at non-integer offsets.

Proof:

Assume that such fault line exists. It cannot go through the leftmost and rightmost square, so it must go through both tiles. Then the following equation should hold: $$\frac{mi}{n} + 1 = \frac{mj}{n} \\ mi + n = mj \\ m(j-i) = n$$ which is obviously impossible, because $m$ and $j-i$ are integers and $m>n$.

Back to the second claim:

The lemma shows that the shaded cells in the following diagram block all vertical fault lines at non-integer offsets, which completes the proof that this tiling, when scaled up by the factor of $n$, gives the fault-line-free tiling of a large rectangle using $m×n$ tiles.


As a demonstration of the construction, here are 2×5 tiles covering a 30×22 rectangle and 3×4 tiles covering a 36×27 rectangle, "seamlessly". You can see how 1×5 and 1×4 tiles are embedded in each tiling.

$\endgroup$
2
$\begingroup$

Here is a partial answer. It proves a fault-free rectangle can be assembled from rectangles of size mxn such that one dimension is not a multiple of the other.

The remaining cases can be converted to the 1xn case solved earlier by Bubbler.

It is really simple. Here is the solution for size 3x4.

A central rectangle is surrounded by four large squares made of n times m rectangles. The gaps at the corners are just the right size for stripes of rectangles. It works for any size mxn.

If m,n are such that one is not a multiple of the other then the grey lines are guaranteed not to align across the black lines, at least not across the black lines touching the central rectangle. This makes the rectangle fault-free.

enter image description here

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