8
$\begingroup$

A P-pentomino is a polymino of the form

A P-pentomino

What I'm curious about is what kinds of rectangles can be tiled with one-sided P-pentominoes. By one-sided, I mean we are only allowed to translate and rotate it, with reflection not allowed. It seems that a $m\times n$ rectangle has a tiling if and only if one of $m,n$ is divisible by $5$ and the other is even, but I'm not sure how to prove this.

Another thing I noticed is that if a rectangle has a tiling, then the tiling must be comprised of rectangular units of the form

A rectangle comprised of a pair of P-pentominoes

I've tried a colouring/parity argument, but this doesn't seem to work, as each tile has an odd number of cells. It can be proven that a $5\times n$ rectangle can be tiled if and only if $n$ is even by considering possible configurations of the tiles on one end of the board and reducing the tiling to the $5\times(n-2)$ case, but I'm unsure how to prove this for the $10\times n$ and beyond case. Any insight is greatly appreciated :)

Edit: to elaborate my proof for the $5\times n$ case, the bottom left corner must be tiled with one of four possible orientations of the tile. Two of those are obviously impossible:

enter image description here

If it is oriented this way, then there must be another tile to complete a $5\times 2$ rectangle, so we reduce the rectangle to the $5\times (n - 2)$ case:

enter image description here

Finally, if it is oriented this way, we arrive at a contradiction by observing each possible way to fill the rest of the rectangle:

enter image description here

$\endgroup$
7
  • 2
    $\begingroup$ Clearly at least one of the dimensions is a multiple of 5 (because the area must be a multiple of 5). You wrote that the other dimension has to be a even, but this is not true since for example 7x10 is easily tilable using 2x5 rectangles. It does seem to be the case that at least one of the dimension has to be even, but I don't know why. $\endgroup$
    – Jaap Scherphuis
    Commented Aug 13 at 8:02
  • $\begingroup$ Your proof (that in a $5\times n$ rectangle $n$ must be even) doesn't work, because it rests on your false assumption that the tiling must be built with $5\times 2$ rectangles. $\endgroup$
    – TonyK
    Commented Aug 13 at 12:26
  • $\begingroup$ @TonyK It doesn't. Observe the left side of the board. In the top left corner, there needs to be a tile which can be oriented in one of four ways. We can scrap two of those orientations right off the bat since the rest of the board can't be tiled in this case. The orientation with one square in the third row implies that a second tile must complete the $5\times 2$ rectangle hence we reduce to the $5\times(n - 2)$ case. The orientation with one square in the third column also leads to a contradiction. $\endgroup$
    – Natrium
    Commented Aug 13 at 12:54
  • $\begingroup$ The orientation with one square in the third row does not imply what you claim $-$ the tile underneath it might have its fifth sub-square pointing to the right, leaving the square in the third row and second column empty. Perhaps further argument can show that this is not possible; but you haven't shown that yet! $\endgroup$
    – TonyK
    Commented Aug 13 at 14:34
  • $\begingroup$ @TonyK correction: Bottom left corner. I was working with mirror images of the tiles. Just reflect everything about the third row $\endgroup$
    – Natrium
    Commented Aug 13 at 15:16

2 Answers 2

Reset to default
10
$\begingroup$

It seems that such a tiling does not need to be made up of $5\times 2$ rectangles. Consider Tiling 10x10

Added: @JaapScherphuis commented that while one side must clearly be a multiple of $5$, the other side does not need to be even and you could have $10 \times 7$ using rectangles. Here is an illustration below of that.

Tiling 7x10

These two examples could slot together if you wanted a $10\times 17$ example not just using rectangles.

$\endgroup$
2
  • $\begingroup$ So side lengths of $1$ and $3$ are easily seen to be impossible, a side length of $5$ is possible if and only if the other side is even, and all other rectangles are possible if and only if one of the sides is a multiple of $5$. $\endgroup$
    – Paul Sinclair
    Commented Aug 13 at 11:51
  • 2
    $\begingroup$ @PaulSinclair - The remaining question is whether one side needs to be even. Is $15\times 7$ possible? $\endgroup$
    – Henry
    Commented Aug 13 at 12:07
4
$\begingroup$

Your question is completely resolved by Theorem 5.11 in the source cited at the end.

Theorem: If you can tile an $m\times n$ rectangle with rotated copies of a one-sided $\mathrm{P}$-pentomino, then $mn$ is even.

Reid proves this using the tile homotopy group, invented by Conway and Lagarias. Specifically, he shows that a $(10a+5)\times (10b+5)$ rectangle cannot be tiled for $a,b\in\mathbb N$. This is sufficient, because if you could tile an $m\times n$ rectangle where $mn$ is odd, then combining copies of that rectangle would produce a tiling of a $(10a+5)\times (10b+5)$ rectangle for some $a,b\in \mathbb N$.

Letting $G$ be the tile homotopy group for the one-sided $\mathrm P$-pentomino, Reid shows that the boundary word for a $(10a+5)\times (10b+5)$ rectangle, $\partial R=x^{10a+5}y^{10b+5}x^{-10a-5}y^{-10b-5}$, is nonzero in $G$. He does this by giving a homomorphism $\varphi:G\to S_{64}$ for which $\varphi(\partial R)$ is nonzero, where $S_{64}$ is the symmetric group on $64$ elements. The definition of this homomorphism is given by $$ \begin{array}{cll} \varphi(x) &= (1, 2, 4, 47, 16, 27, 41, 54, 56, 9)(3, 6, 12, 11, 34, 50, 62, 61, 49, 58)\\ &\phantom{= } \,\,(5, 10, 19, 32, 24, 36, 31, 37, 42, 55)(7, 14, 23, 28, 43, 57, 52, 40, 38, 46)(8, 59)\\ &\phantom{= }\,\,(13, 21, 35, 51, 20, 15, 25, 17, 18, 30)(22, 33, 48, 60, 64, 26, 39, 53, 63, 44)(29, 45) \\\varphi(y) &= (2, 3, 5, 9, 17, 28, 42, 12, 14, 22)(4, 7, 13, 6, 20)(8, 25, 37, 11, 33) \\ &\phantom{= }\,\,(10, 18, 29, 44, 58)(15, 24, 30, 46, 57, 63, 62, 48, 54, 47)(16, 26, 38, 50, 61)\\ &\phantom{= }\,\,(19, 31, 39, 45, 21, 34, 49, 51, 59, 64)(27, 40)(32, 36, 52, 35, 41)(43, 56, 60, 55, 53) \end{array} $$ It is routine to show that $\varphi$ is a well-defined homomorphism, in the sense that $\varphi(\partial T)=0$ when $T$ is one of the rotations of the $\mathrm P$-pentomino. Furthermore, it is routine to check that $\varphi(x^{10a+5}y^{10b+5}x^{-10a-5}y^{-10b-5})\neq 0$, via a tedious computation in $S_{64}$.

The fact that this proof-certificate is so complicated shows that this is a really hard problem! Reid further proves that this problem is hard by demonstrating that there cannot be a "coloring argument" which disproves this tiling (think of the mutilated chessboard problem, where you prove impossibility by counting white and black squares).

Reid, Michael. (2003). Tile homotopy groups. Enseignement Mathématique. 49. 123-155. https://doi.org/10.5169/seals-66684

For anyone like me who is curious about the variant of this problem where you allow reflections, it turns out then that you can tile some odd $\times$ odd boards. The only boards you cannot tile are $1\times n$, $3\times n$, and $5\times \text{odd}$. Below is a tiling of a $7\times 15$ board, taken from https://polyominoes.org/data/5P. Together with this, and the $2\times 5$ rectangle, you can make all larger rectangles.

enter image description here

$\endgroup$
2
  • 2
    $\begingroup$ The case when reflected tiles are allowed is solved. A tiling of a $7\times 15$ rectangle is given here: polyominoes.org/data/5P It can be proven by elementary means that the only rectangles of the form $5k\times n$ that cannot be tiled are ones where $n = 5$ and $k$ is odd, and the case where $n$ is odd and either $n\in \{1, 3\}$, or $k=1$. The rest can be tiled by combining this $7\times 15$ tiling with $2\times 5$ tilings. $\endgroup$
    – Natrium
    Commented Aug 13 at 18:03
  • 1
    $\begingroup$ Thank you for sharing the reflections-allowed result, Natrium! $\endgroup$
    – Mike Earnest
    Commented Aug 13 at 21:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .