Does one pieces of every kind of connected polyominoes P in $\mathbb{R}^2$ which has no hole cover a plane?

Question

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.

Answer 1

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.

Answer 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.