21
$\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 Jan 15 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 Jan 15 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 Feb 1 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 Feb 2 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 Feb 5 at 18:54
6
$\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 Feb 4 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 Feb 4 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 Feb 4 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 Feb 4 at 16:51
  • 2
    $\begingroup$ @MishaLavrov: It can strongly surround a hole as shown here. $\endgroup$ – RavenclawPrefect Feb 4 at 17:09

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.