2

Or polyominoes with no hollow in $\mathbb{R}^3$?

I created this conjecture and tried to make counterexample, but it doesn't work well. Thank you for any answer or correcting question.

Takahiro Waki
  • 141

2 Answers2

9

I think one can do this by standard inductive trickery.

First take a square grid in the plane. Index the union of the set of cells and the set of polyominoes by natural numbers $i$.

At each stage $i$, we will have placed $n_i$ connected polyominos with no holes in the plane so that they form a single connected polyomino. We wish to either place a polyomino covering a given cell (if we haven't already) or to place a particular polyomino (if we haven't already).

If we have already fulfilled the condition, don't place any polyomino and move on to the next stage.

If we haven't yet covered the cell, choose a path in the grid connecting that cell to the union of the $n_i$ already existing polyominoes, then enlarge the path to fill in any holes, then further enlarge it to ensure it is a polyomino not already used, then place it.

If we haven't yet included the polyomino, place the polyomino somewhere far away from the existing polyominoes, then add a path connecting it to the union of the $n_i$ already existing polyominoes, enlarge this path to fill in any holes, and further enlarge it to ensure it is a polyomino not already used (including the one just placed), and place it.

If we iterate this procedure over all natural numbers $i$, we will cover all the squares using all the polyominoes, as desired.

Will Sawin
  • 135,926
  • 2
    It can't be too arbitrary, as you don't want to make new holes, or cause a tile to be needed in more than one place. Gerhard "Patch Up Holes In Argument" Paseman, 2017.04.30. – Gerhard Paseman May 01 '17 at 03:54
  • @GerhardPaseman If I place it sufficiently far from the existing tiles, neither of these can happen. – Will Sawin May 01 '17 at 13:54
  • 1
    Of course it can be made to work. It may be more clear to say: On turn 2i, cover without overlap the smallest numbered uncovered cell with an unused polyomino so that the remaining unfilled region stays connected, and on turn 2i+1, place smallest numbered unused polyomino without overlap so that the remaining unfilled region stays connected, but otherwise arbitrarily. This then gives a tiling by induction. Gerhard "Not Much More Is Needed" Paseman, 2017.05.01. – Gerhard Paseman May 01 '17 at 14:10
  • @GerhardPaseman Sure, except you also need to specify that it is connected with no hole - otherwise you could produce a 1-square hole when the size 1 polyomino is already used, say. – Will Sawin May 01 '17 at 14:22
  • Note that you can modify the above to include some polyominoes with holes, so that a few more polyominoes are used. Gerhard "Not All Of Them, Unfortunately" Paseman, 2017.05.01. – Gerhard Paseman May 01 '17 at 14:31
  • That is why with each placement, you require that the unfilled region be connected. Polyominoes with holes can be accommodated only if there are existing covered regions that fill those holes precisely, or combinations of unused polyominoes that (when placed together as a group) help maintain the invariant of the unfilled region being connected. Gerhard "Arbitrary Up To Some Constraints" Paseman, 2017.05.01. – Gerhard Paseman May 01 '17 at 14:43
  • @GerhardPaseman You should probably also require that the filled region be connected. If the unfilled region contains an shape like the letter P, where the line coming out is one square thick, there may be no way to fill it using polyominoes without holes that weren't used already. – Will Sawin May 01 '17 at 15:00
  • Because the unfilled region is connected and infinite, there are infinitely many polyominoes that will fit there. Some of them will be unused. Gerhard "So You Are Still Covered" Paseman, 2017.05.01. – Gerhard Paseman May 01 '17 at 15:03
  • Granted, if you are using only polyominoes without holes, then you want the unfilled region to have at most one hole. This can be done, but I still think "arbitrarily" is a word far from optimal in describing the process. Gerhard "It's How You Say It" Paseman, 2017.05.01. – Gerhard Paseman May 01 '17 at 15:07
2

Will Sawin's answer is a good one. This post is to point out that a similar argument works for arbitrary finite dimensions, and many other regions. Here is the process abstracted.

Given a region R of sufficient connectivity with a countably infinite number of cells, and an enumeration of those cells, and given a countably infinite and varied list (with enumeration) N of necessary tiles (which may or may not have repeats), and given a list L of additional helper tiles which may or may not be used, tile R using all of N and maybe some of L.

The key is finding the right invariant properties to preserve so that the following induction works, and gives the desired result:

On even numbered steps 2i, make sure the uncovered cell with the smallest number is covered with an as yet unused tile from either N or L, while preserving the invariant (and then update the lists of uncovered cells and unused tiles), and

On odd numbered steps 2i+1, place the unused tile from N with the smallest number in the region on uncovered cells, again preserving the invariant. Again, update the lists afterward.

Will Sawin is implicitly using the invariant that the covered region is simply connected and finite, which implies the uncovered region is connected and infinite and has at most one hole, so his list L is empty and unnecessary. I allow some list L of polyominoes with holes, and just need the uncovered region to be infinite and connected. Since in both our cases N and L are sufficiently varied, we are guaranteed to accomplish each step and preserve the invariant. Some work needs doing, for example having each tile in N and L being finite but having unbounded sizes helps, so that the complement stays infinite.

This general method is part of recursion theory, and variants where you are allowed to depart from the invariant often are known as priority methods with injury. Indeed, it is reasonable to view much of recursion theory from a tiling perspective. Thus the poster's conjecture is a very special case of what is possible.

Gerhard "Next Comes Countable N-Category Theory" Paseman, 2017.05.01.

Gerhard Paseman
  • 12,968