One rectangle, indivisible

Question

Here is a rectangle made out of 2x1 dominoes:

It can be divided along a line into two smaller rectangles:

What is the smallest (in area) rectangle of (edit) multiple 2x1 dominoes that cannot be split along a line into two smaller rectangles?

Answer 1

The best you can do is one with an area of 30 (5 x 6):

Disproving smaller cases

2 x 2 and 2 x 3

For a 2 x 2 rectangle there's only one possible orientation, which can obviously be sliced. For 2 x 3, there are two arrangements, each of which can also be sliced.

2 x anything

In any rectangle with a side length $l$ of 2, you can't have any domino aligned so that its long side is aligned with $l$ because that would provide an immediate cut point. The only other option is to have the long side of all dominoes 90° compared to $l$, which provides cut points after each stacked pair. (Or if you try to offset the pairs, leads to an unfillable gap of 1x1 at the ends.)

3 x 3

Is an odd number of tiles (9) and thus can't be tiled by 2 x 1 dominoes.

3 x 4

A 3 x 4 rectangle has one end (let's make it the top) of length three, and thus must begin like this:



But whichever way we try to fill the second position in the second row (horizontal or vertical) we end up with a cut site.

3 x anything

A side length of 3 will never work. Based on the second picture above (3x4), you must always start the top the same way, and then must always alternate magenta dominoes down the side. If it's an even number (3x6, 3x8, ...) you'll end up with a cut site like the one shown in the 3x4 diagram, on the second vertical. If it's an odd number, you'll end up with an unfillable 1x1 square at the bottom right.

4 x 4

Let's put a domino into the top left to get started (this covers all possible orientations as well). Once we've done that, we can't fill box 3 with a horizontal domino, because that would create a cut site on the first horiztonal. So we put a vertical domino in box 3, which means there must be a vertical one in box 4. Now box 12 can't be filled with a vertical domino, because that would create a cut site along the third vertical, so we must go horiztonal to fill box 12. And since box 16 is only height 1, we have to put another horizontal one there, which leaves a cut site on the second vertical. So there's no way to do this one.

4 x 5

In this case, there are two "top" configurations to consider. For the first (hor-vert-vert), we can see then that box 6 must have a vertical domino, otherwise we'd be able to cut on the second horiztonal. That means block 5 must also have a vertical since it's width one. By the same reasoning, blocks 11 and 12 must have vertical dominoes, and again 14 and 13. But that allows us to cut right down the middle, so no dice here.



The other top configuration (excluding the obviously wrong hor-hor and vert-vert-vert-vert, as well as reflection of the above one) is vert-hor-vert. In this case, we then see that box 6 (and 7) must have vertical dominoes to eliminate the cut at the second horizontal. That means squares 9 and 12 must also have vertical dominoes since there's no other way to fill them. But then whichever way we try to put a domino to cover box 14, we allow a cut site. If it's horizontal, you can cut at the 4th horizontal line. If it's vertical, you can cut at the first vertical line.

4 x 6

In the first top configuration (same as 4 x 5 above), you'll have the same problem, just one step further down as you continue (either way you fill box 19, you'll introduce a cut site).

In the second top configuration (same as 4 x 6 above), you must place the domino on box 14 vertically to avoid the 4th horizontal cut site, but that means below the domino in box 9 must be another vertical one, which allows a cut on the first vertical. Again, failure.

5 x 5

Again, odd number of squares (25) and so can't be tiled.

So that's definitely not an elegant mathematical proof, but I think it'll hold up. And since the image at the top of this answer shows that 5x6 can be done, that is the smallest possible answer.

Answer 2

Here is a proof that 5x6 is the smallest possible rectangle.

A rectangle of size $x$ by $y$ has $\frac{xy}{2}$ dominoes and $x+y-2$ potential lines. All of these lines must be blocked by at least one domino which has one square on each side. However, if the line divides the rectangle into two even areas, then one domino blocking it would leave an odd area on each side, so there must be a second domino also blocking that line. A domino can't block more than one line at once, so there must be at least one domino for every line making odd areas and two for every line making even areas.

Either both dimensions of the rectangle are even or one is even and one is odd. Suppose both are even, so the rectangle is $2m$ by $2n$ units for positive integers $m$ and $n$. Then every line is even, so at least $2(2m+2n-2)$ dominoes are required. There are $2mn$ dominoes, so $2mn\ge2(2m+2n-2)$. Rearranging, $(m-2)(n-2)\ge2$. The smallest possible $m$ and $n$ are $4$ and $3$, making an $8$-by-$6$ rectangle with an area of $48$.

Otherwise, one dimension is odd and the rectangle is $2m+1$ by $2n$ units for positive integers $m$ and $n$. Now there are $n$ odd lines (every other line running parallel to the odd edge) and $2m+n-1$ even ones, so $(2m+1)n\ge2(2m+n-1)+n$, which rearranges to $(m-1)(n-2)\ge1$. Now the smallest possible values are $m=2$, $n=3$, making a $5$-by-$6$ rectangle with an area of $30$.

Answer 3

I'll one-up you guys and prove this stronger statement: If $m\geq n$ are the dimensions of a rectangle that admits a nonsplittable domino tiling using more than one domino, then $m \geq 6$ and $n \geq 5$.

It's stronger because it also proves the nonexistence of very long yet thin nonsplittable domino tilings, such as $60\times3$ or $999 \times 4$.

Proof:

First we'll show that if a rectangle admits a nonsplittable tiling using more than one domino, neither dimension may be $4$ or less.

Let $m \geq n$ be the dimensions of a rectangle, and assume that the rectangle is aligned in portrait. Note that $m \cdot n$ must be even, otherwise you can't cover the rectangle with an integer number of dominoes (each of area $2$). We'll show case-by-case that $n$ can be neither $1, 2, 3$ nor $4$.

Case $n = 1$: For any tiling of a $m\times1$ rectangle, there is a split along the bottom edge of the topmost domino.

Case $n = 2$: For any tiling of a $m\times2$ rectangle, there needs to be at least one horizontal domino, otherwise there would be a vertical split along the middle. Now either the top edge or the bottom edge of this domino induces a horizontal split.

Case $n = 3$: By necessity, there are at least two horizontal dominoes, one to prevent each vertical split. If such a horizontal domino were not touching either the top or bottom edge of the rectangle, either the top or bottom edge of this domino induces a split (since the two dominoes required to block both splits would overlap). So we need exactly two horizontal dominoes, in opposite corners of the rectangle. Every other domino must be vertical.

Now consider the left column of the rectangle. One square of this column (either the top or the bottom square) is covered by one of the two horizontal dominoes, the other $m-1$ squares are covered by vertical dominos, so $m-1$ is even. But since $m\cdot n$ is even and $n = 3$, $m$ is even too, which gives a contradiction.

Case $n = 4$:

Suppose a horizontal split (at height $k$) were prevented by a single domino. This split divides the rectangle into two pieces, the bottom piece (of even area $4k$) would then be covered by a half domino and some whole dominoes, so it would have odd area. Contradiction.

So we know that each horizontal split is prevented by at least two (vertical) dominoes. Since there are $m-1$ such splits, there must be at least $2m-2$ vertical dominoes, and since there are $2m$ dominoes in total, there can be at most $2$ horizontal dominoes, which are not enough to prevent the $3$ possible vertical splits.

Okay, so now we've done all four cases, we have $m \geq n \geq 5$ for nonsplittable tilings. Since $25$ is odd, $m = n = 5$ isn't coverable in an integer amount of dominoes, so we get $m\geq 6$ and $n \geq 5$ as a new lower bound. $~~~~\square$

Answer 4

Before the question was edited, this was a valid answer:

A single domino makes a rectangle that cannot be split along a line into two smaller rectangles.

Here's my new answer:

A 3x3 rectangle is the smallest using multiple dominoes:

Answer 5

Sorry if this goes against the spirit of your puzzle. No proof here, just a baseline answer:

5X6, 30

And one possible configuration is:

Answer 6

N.B.: At the time of posting, this was a partial answer dealing with a case that hadn't been ruled out. It has now been superseded by the more complete answers by Dan Russell and f''.

---

Concerning the 5x4 rectangle:

Here is a proof that the 5x4 rectangle cannot be tiled in a "split-free" way. Consider a grid that is four columns wide and five rows tall: If the filling is to be "split-free", then there must be at least one domino spanning Column 2 and Column 3. This domino cannot be placed in Rows 2, 3, or 4, because of the effects of the other two dominoes that also overlap this row. They would either both "point" up from this row or both point down from this row, creating a split; or one would "point" up and the other down. This latter case would divide the grid into two disconnected regions with an odd number of tiles remaining, neither of which could be tiled by dominoes. Thus, if such a tiling exists, there must be a domino in the center of the top row or the bottom row. Without loss of generality, assume that it is in the top row.

Now note that

there must also be at least one domino spanning Column 1 and Column 2, and another domino spanning Column 3 and Column 4. Neither of these can be in the second row, since we have already placed a domino in the center of the first row, and placing either of our new dominoes in an adjacent row would leave a single corner tile isolated and uncovered. Similarly, our two new dominoes cannot be in adjacent rows or in the same row, since this would necessarily create a split between two of the rows. Thus, these two new dominoes can only be in Row 3 and Row 5, respectively.

Once you have done this,

It is not hard to see that the remaining grid cannot be filled without creating a split between the second and third rows.