4
$\begingroup$

Call a finite collection of tiles that can tile the plane if we have to use each tile at least once tiling.

Is there a collection of at least 3 tiles that is not tiling, but such that after removing any one tile from it we get a tiling collection?

For example, a set of two non-compatible, tiling singleton tiles is such a collection.
I intentionally didn't define what I mean by tile because I'm interested in all sorts of constructions - it can be Wang tiles or your favorite geometric connected or disconnected polygonal or (simply) connected region with translations or rotations.
It is easy to see that on a line we cannot have such a collection of at least 3 Wang tiles.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ "Hyponontiling" is a difficult sequence of letters for my brain to process, although I now see how to read it. Possibly "critical nontiling" would be a better name for this concept. $\endgroup$
    – Sam Hopkins
    Commented Mar 10 at 21:30
  • $\begingroup$ Better but less funny. $\endgroup$
    – domotorp
    Commented Mar 10 at 21:33
  • $\begingroup$ It might be possible to prove no such Wang tile set exists by constructing equivalent Turing machines. There's some technical difficulties and you have to make some particular assumptions (or at least be content with an answer in one quadrant of the plane). The key is the halting states; halting="does not tile plane". You start with at least one, and need to remove a state (tile) and end up with none (tiles the plane). So show after removing any single state (any single tile), you will have at least one more halting state than you want (except for the time you remove the state that will halt) $\endgroup$
    – Ben Burns
    Commented Mar 13 at 15:04
  • $\begingroup$ Side note: Just because a Turing machine defines a state doesn't mean it is used. However, the definition of the problem says every tile (state) is used at least once, therefore, if there is a halting state, the machine will halt. $\endgroup$
    – Ben Burns
    Commented Mar 13 at 15:08

0

Reset to default

You must log in to answer this question.