37
$\begingroup$

Here is a rectangle made out of 2x1 dominoes:

2x1 dominoes arranged into a rectangle

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

Splitting the big rectangle 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?

$\endgroup$
  • 14
    $\begingroup$ Maybe I am missing something, but what if you have just one domino? It's area is 2 and it cannot be split along a single line into two smaller rectangles. $\endgroup$ – Ovi Jun 30 '16 at 19:31
  • 1
    $\begingroup$ Are the two rectangles supposed to be equal in size? $\endgroup$ – APrough Jun 30 '16 at 19:44
  • $\begingroup$ @APrough We can assume not, because it was not stated, but also because then the solution would be trivial. $\endgroup$ – Roland Jun 30 '16 at 19:45
  • $\begingroup$ @Ovi Good thought. I totally forgot about that :/ $\endgroup$ – Owen Jun 30 '16 at 20:26
  • $\begingroup$ @Owen Just say (except for the 1x1) in your puzzle. $\endgroup$ – Insane Jul 1 '16 at 3:07
28
$\begingroup$

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

image description

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.

enter image description here

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:

enter image description here

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

enter image description here

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.

enter image description here

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.

enter image description 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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ I think the best way to prove this is just to show that if any dimension is 4, the rectangle can be split (I think I've got it, but it's gonna take forever to paste the dang images, so you should go ahead if you can). Next smallest is then 5X6 since 5X5 is excluded. $\endgroup$ – Roland Jun 30 '16 at 20:53
  • $\begingroup$ What is interesting about this solution is that I can't figure out a way to divide it into 3 or 4 rectangles either (5 yes). I wonder if it's possible to have large rectangles not divisible except into a large number of sub rectangles. $\endgroup$ – Owen Jun 30 '16 at 21:08
  • 1
    $\begingroup$ What about $3\times 6$ or $2 \times 7$ or $2 \times 8$? $\endgroup$ – Anon Jun 30 '16 at 21:08
  • $\begingroup$ @McFry Good point! My brain: 8 is bigger than 5, so I don't have to deal with it. Two dimensions, here, brain. (I added some comments in general about any rectangle with a side of 2 or 3.) $\endgroup$ – Dan Russell Jun 30 '16 at 21:22
  • $\begingroup$ Here's a follow-up question — what's the smallest domino tiling that follows both the no-dividing-line constraint and the tatami-layout constraint (which is that no four dominoes can meet at a corner)? $\endgroup$ – Joe Z. Jul 1 '16 at 4:26
24
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice! I figured someone would provide a more mathematical solution. I think the key intuition here is the leaving-odd-numbers when an even-dividing line is bridged. $\endgroup$ – Dan Russell Jun 30 '16 at 20:59
  • $\begingroup$ I was curious, so I checked whether the 6x8 case could also be realized. The answer is yes. $\endgroup$ – Michael Seifert Jun 30 '16 at 21:24
13
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Your first statement is the same as "no dimension may be 4 or less". $\endgroup$ – Roland Jun 30 '16 at 21:10
  • $\begingroup$ That is better phrasing, yes. $\endgroup$ – Anon Jun 30 '16 at 21:16
6
$\begingroup$

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:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ If we are to take the plural "dominoes" in "rectangle of 2x1 dominoes" to mean any number (inluding 1), then I direct @Owen to xkcd.com/169 $\endgroup$ – Roland Jun 30 '16 at 20:11
  • $\begingroup$ @Roland. A portion of a plural quantity can be a single unit. $\endgroup$ – User4407 Jun 30 '16 at 20:16
  • $\begingroup$ The question has been edited to rule this out now. $\endgroup$ – Dan Russell Jun 30 '16 at 20:28
  • 1
    $\begingroup$ @PédeLeão I am aware, just as the xkcd puzzle is technically correct also. This is an interesting question with a potentially interesting solution; the trivial exception should thus be ignored, as is now made explicit in the edit. $\endgroup$ – Roland Jun 30 '16 at 20:41
  • 1
    $\begingroup$ I drew the same, the question does not explicitly state we must tile (although it is fairly reasonable to assume it was meant). $\endgroup$ – Jonathan Allan Jun 30 '16 at 23:39
4
$\begingroup$

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

5X6, 30

And one possible configuration is:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Looks like we got reflections of one another within 20 seconds! $\endgroup$ – Dan Russell Jun 30 '16 at 19:55
  • 2
    $\begingroup$ All my life, Microsoft Office has been trying to snap things into place when I don't want it to. The one time I could finally make use of it, it refuses to. Ugh... $\endgroup$ – Roland Jun 30 '16 at 19:58
  • $\begingroup$ Ah, the irony of Office. $\endgroup$ – Dan Russell Jun 30 '16 at 20:05
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is not an answer. $\endgroup$ – The Great Duck Jul 1 '16 at 20:11
  • $\begingroup$ At the time I posted it, it was a case that hadn't been ruled out. I've put a disclaimer at the top to reflect this. $\endgroup$ – Michael Seifert Jul 2 '16 at 13:00
  • $\begingroup$ But it is still not an answer. You have not answered the puzzle. $\endgroup$ – The Great Duck Jul 2 '16 at 15:36

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.