2
$\begingroup$

Suppose you have a (finite) figure $F$ and a polyomino $P$ with the same symmetries as a square that tiles $F$. It seems obviously true that the tiling must be unique, but I cannot find a nice proof of this.

There is a generic proof described below that can work in any specific case I looked at, but to make it completely general seems very technical. I am hoping there is some obvious insight I am missing, or maybe some algebraic fact I don't know.


Partial proof: If the figure has only one tile, its tiling is unique. Suppose all figures tileable by $P$ with $n$ tiles is uniquely tileable, and consider a figure $F$ with $n + 1$ tiles. Identify some "feature" (such as a corner). Prove the feature exists at the border of $F$. Prove the tile can only fit in the feature in one way. Now the rest of the figure has $n$ tiles and it's tiling is therefor unique, and so our tiling of $F$ must be unique. And so all tilings by $P$ are unique.

The feature is tile-specific. For example, for the square tetromino, it's a "corner", for the X pentomino it's a peak (a cell with only one neighbor). The feature is a piece of both $P$ (and as is proven) of $F$.

We prove the feature exists at the border using a modification of the answer to this question: Does every domino tiling have exposed dominoes? The basic idea is to start at some tile, and check if the feature of that tile is at the border; if it is we found it; otherwise, some tile(s) "covers" it and we consider one of them next, until we eventually end. (Some care must be taken to avoid loops, see the full answer for details in that specific case.)


The problem with this is

  1. Finding a general definition for a suitable feature that will work for any tile.

  2. Making the walking procedure generic enough that it will always work. For example, for the square tetromino, we always have to walk in a up-right (or some other diagonal) direction; for the X pentomino we always have to walk up (or some other orthogonal direction).

$\endgroup$

1 Answer 1

2
$\begingroup$

The leftmost grid-square in the uppermost row of $F$ can only be filled by the leftmost grid-square in the uppermost row of $P$.

The leftmost grid-square in the uppermost row exists for every $F$ and every $P$ and is clearly on the border of $F$.

$\endgroup$
1
  • $\begingroup$ Very straightforward; I almost feel foolish for missing something that's so obvious once pointed out o.0. Thanks for posting the answer. $\endgroup$ Commented Nov 29, 2017 at 22:09

You must log in to answer this question.

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