24
$\begingroup$

Given a polyomino $P$, we can ask if it is possible for disjoint copies of $P$ to surround a single cell in the square grid - i.e., for the complement of their union to have a connected component of size $1$.

We can further refine this into polyominoes that weakly surround a cell (just covering the four edge-adjacent cells) and those that strongly surround a cell (covering all $8$ squares which share a vertex with the hole). Thanks to Julian Rosen for clarifying this distinction.

My original intuition was that this is always possible, but I was having trouble proving it; after enough struggling to show it was true, I started searching for counterexamples. Here is a polyomino with $48$ cells which does not even weakly surround a one-celled region, which is not too difficult to verify by hand:

                                                    enter image description here

After some modifications, I've reduced this down to a simply-connected solution with $26$ cells:

                                                    enter image description here

I have a size-$23$ example of a polyomino which does not strongly surround a hole:

                                                    enter image description here

What is the smallest polyomino that cannot surround a single-celled hole? I am interested in this question for both the weak and strong cases.

I've written some code to explore this, and have confirmed that all of the $1,227,708$ free polyominoes on at most $14$ cells can strongly surround a hole. How much can we tighten these bounds?

$\endgroup$
19
  • 4
    $\begingroup$ I am not asking whether polyominoes tile the plane; I'm asking whether the complement of disjoint copies of them can have connected components of size $1$. Here is an image of a polyomino surrounding a $1\times 1$ hole, for reference. $\endgroup$
    – RavenclawPrefect
    Commented Jan 15, 2021 at 16:46
  • 2
    $\begingroup$ Is it correct that to surround a square, we should cover the 8 adjacent squares (including the diagonally adjacent ones)? $\endgroup$
    – Julian Rosen
    Commented Jan 15, 2021 at 22:24
  • 1
    $\begingroup$ This is just a idle thought, but what about looking at the problem in reverse; i.e., given a unit square hole (either weakly or strongly surrounded), establish some kind of constraint on how its neighbors may be connected, which in turn limits the features of a polyomino that cannot leave such a hole. Perhaps this is too nebulous or difficult but it was just something that seemed to offer a different perspective than generating polyominoes and then seeing if they can be arranged to leave such a hole. $\endgroup$
    – heropup
    Commented Feb 1, 2021 at 20:54
  • 1
    $\begingroup$ Your size-$23$ upper bound is nicely symmetric. It would be easier to verify (if true) that there are no smaller examples with that symmetry. $\endgroup$
    – mjqxxxx
    Commented Feb 2, 2021 at 22:07
  • 2
    $\begingroup$ I just wanted to comment on what a nicely formulated problem this is (can't +1 more than once!) It's simply stated but the answer is non-trivial. Also, in a sense this is the hardest problem of this type. A natural generalization is to look for minimal polyominoes that cannot (strongly) surround a hole of shape $P$, for some polyomino $P$. For all $P$ with size > $1$ that I've checked, the minimal polyominoes have size $\le 11$, making them easy enough to find through exhaustive search. $\endgroup$
    – mjqxxxx
    Commented Feb 5, 2021 at 18:54

1 Answer 1

Reset to default
9
$\begingroup$

This is by no means a complete answer, but as I mentioned in my last comment, we can make some headway by restricting a computer search to particular symmetry classes. I've been able to check all the free polyominoes of size $N \le 23$ that have a horizontal or vertical symmetry axis (a class that contains OP's size-$23$ non-strongly-surrounding example). Within this symmetry class, there are no non-weakly-surrounding examples of size $N \le 23$, and the smallest non-strongly-surrounding examples have size $N=23$; so OP's example is minimal. Of the $464188$ size-$23$ free polyominoes with a horizontal or vertical axis of symmetry, there are just two that cannot strongly surround a single cell: the example given in the question, and the polyomino pictured below.

                                                    non-strongly-surrounding symmetric polyomino

Heuristically, one might expect minimal examples to have some symmetry, because symmetric polyominoes have the fewest "different-looking local regions", and hence the fewest different possibilities for packing local regions around a hole. Next steps, then, might be to check the other two large symmetry classes for free polyominoes: $180^\circ$ rotational symmetry around a point, and reflection symmetry across a diagonal.

Update: Checking the polyominoes with rotational symmetry around a point turned up the following minimal (within that class) non-strongly-surrounding example, with size $20$:

                                                    non-strongly-surrounding rotationally symmetric polyomino

Second update: Checking the polyominoes with a diagonal reflection symmetry, there are exactly two minimal (within that class) non-strongly-surrounding examples with size $19$. One is formed by removing an interior cell from the previous example (as already pointed out in a comment), and the other is new:

                                 enter image description here enter image description here

Third update: In order to make progress on the non-weakly-surrounding case (which is a more stringent criterion, so the minimal examples are at least as large), I looked at polyominoes with both vertical and horizontal reflection symmetries. The size-$25$ example below provides an improved upper bound for this case.

                                                    enter image description here

$\endgroup$
6
  • $\begingroup$ Thanks for this investigation! I notice that both your example and the one in the OP have the line of reflection passing through a cell; did you also check cases where the line coincides with edges between cells? (Obviously this doesn't have $N=23$ examples, since the number of cells must be even, but perhaps it does for lower even $N$.) $\endgroup$
    – RavenclawPrefect
    Commented Feb 4, 2021 at 15:56
  • 1
    $\begingroup$ @RavenclawPrefect: Yes, the reflection-symmetric cases do include both types of line; I checked polyominoes of both even and odd width. $\endgroup$
    – mjqxxxx
    Commented Feb 4, 2021 at 16:29
  • 4
    $\begingroup$ You can remove one of the central squares in your last picture to get a size-19 example. It loses its rotational symmetry, of course, but it's still symmetric about one of its diagonals. $\endgroup$
    – TonyK
    Commented Feb 4, 2021 at 16:38
  • $\begingroup$ Would this size-16 version not work, then? It also has 180 degree rotational symmetry, but I'm struggling to see how it fails. $\endgroup$
    – Misha Lavrov
    Commented Feb 4, 2021 at 16:51
  • 2
    $\begingroup$ @MishaLavrov: It can strongly surround a hole as shown here. $\endgroup$
    – RavenclawPrefect
    Commented Feb 4, 2021 at 17:09

You must log in to answer this question.

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