2
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman May 1 '17 at 3:54
  • $\begingroup$ @GerhardPaseman If I place it sufficiently far from the existing tiles, neither of these can happen. $\endgroup$ – Will Sawin May 1 '17 at 13:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman May 1 '17 at 14:10
  • $\begingroup$ @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. $\endgroup$ – Will Sawin May 1 '17 at 14:22
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman May 1 '17 at 14:31
2
$\begingroup$

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.

$\endgroup$

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.