Is every “even” polyomino with one hole tileable by dominoes?

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
13
down vote

favorite
3












In Conformal Invariance of Domino Tiling the author defines an even polyomino as a polyomino with all corners (of all borders, inside and outside) "black" if the polyomino is colored with the checkerboard coloring. A corner is black if the interior angle lies in a black square, like this:



enter image description here



Here are some examples:



enter image description hereenter image description hereenter image description here



My question is whether it is true that an even polyomino with one hole is always tileable by dominoes.



Background: A related polyomino is called a Temperleyan polyomino (in the same paper), which is formed from an even polyomino by removing one black corner from the outer border, and appending a black cell to each interior border. Here are some examples:



enter image description hereenter image description here



The paper shows (although not really in a way I can follow) Temperleyan polyomino are tileable by dominoes.



It is also easy to show that the deficiency (black minus white cells) in an even polyomino with $H$ holes is $1 - H$, so an even polyomino with 1 hole is balanced (has the same number of black and white cells).



The holes of even polyominoes are also even.




tiling polyomino




share|cite|improve this question





















  • What prevents the 5 by 3 rectangle with a 2 by 1 hole in the centre from being a counterexample? All corner squares are black. but the number of squares is odd so it can't be tiled.
    – orlp
    Aug 1 at 0:34






  • 1




    If you remove the "outer layer" (any cell with a corner touching the outside) from an even polyomino, do you get an even polyomino? And can the "outer layer" be tiled by dominoes (i.e. is it even length)?
    – Solomonoff's Secret
    Aug 1 at 1:19







  • 1




    @Solomonoff'sSecret I found a proof today, and am busy typing it out. It relies basically on the idea you have.
    – Herman Tulleken
    Aug 1 at 1:23






  • 1




    @HermanTulleken Yes, I strongly believe the answer to both my questions are "yes", from which the conclusion follows by induction.
    – Solomonoff's Secret
    Aug 1 at 1:24






  • 1




    My proof is flawed and not easily fixed and yours takes a fundamentally more sound approach.
    – Solomonoff's Secret
    Aug 1 at 2:02














up vote
13
down vote

favorite
3












In Conformal Invariance of Domino Tiling the author defines an even polyomino as a polyomino with all corners (of all borders, inside and outside) "black" if the polyomino is colored with the checkerboard coloring. A corner is black if the interior angle lies in a black square, like this:



enter image description here



Here are some examples:



enter image description hereenter image description hereenter image description here



My question is whether it is true that an even polyomino with one hole is always tileable by dominoes.



Background: A related polyomino is called a Temperleyan polyomino (in the same paper), which is formed from an even polyomino by removing one black corner from the outer border, and appending a black cell to each interior border. Here are some examples:



enter image description hereenter image description here



The paper shows (although not really in a way I can follow) Temperleyan polyomino are tileable by dominoes.



It is also easy to show that the deficiency (black minus white cells) in an even polyomino with $H$ holes is $1 - H$, so an even polyomino with 1 hole is balanced (has the same number of black and white cells).



The holes of even polyominoes are also even.




tiling polyomino




share|cite|improve this question





















  • What prevents the 5 by 3 rectangle with a 2 by 1 hole in the centre from being a counterexample? All corner squares are black. but the number of squares is odd so it can't be tiled.
    – orlp
    Aug 1 at 0:34






  • 1




    If you remove the "outer layer" (any cell with a corner touching the outside) from an even polyomino, do you get an even polyomino? And can the "outer layer" be tiled by dominoes (i.e. is it even length)?
    – Solomonoff's Secret
    Aug 1 at 1:19







  • 1




    @Solomonoff'sSecret I found a proof today, and am busy typing it out. It relies basically on the idea you have.
    – Herman Tulleken
    Aug 1 at 1:23






  • 1




    @HermanTulleken Yes, I strongly believe the answer to both my questions are "yes", from which the conclusion follows by induction.
    – Solomonoff's Secret
    Aug 1 at 1:24






  • 1




    My proof is flawed and not easily fixed and yours takes a fundamentally more sound approach.
    – Solomonoff's Secret
    Aug 1 at 2:02












up vote
13
down vote

favorite
3









up vote
13
down vote

favorite
3






3





In Conformal Invariance of Domino Tiling the author defines an even polyomino as a polyomino with all corners (of all borders, inside and outside) "black" if the polyomino is colored with the checkerboard coloring. A corner is black if the interior angle lies in a black square, like this:



enter image description here



Here are some examples:



enter image description hereenter image description hereenter image description here



My question is whether it is true that an even polyomino with one hole is always tileable by dominoes.



Background: A related polyomino is called a Temperleyan polyomino (in the same paper), which is formed from an even polyomino by removing one black corner from the outer border, and appending a black cell to each interior border. Here are some examples:



enter image description hereenter image description here



The paper shows (although not really in a way I can follow) Temperleyan polyomino are tileable by dominoes.



It is also easy to show that the deficiency (black minus white cells) in an even polyomino with $H$ holes is $1 - H$, so an even polyomino with 1 hole is balanced (has the same number of black and white cells).



The holes of even polyominoes are also even.




tiling polyomino




share|cite|improve this question













In Conformal Invariance of Domino Tiling the author defines an even polyomino as a polyomino with all corners (of all borders, inside and outside) "black" if the polyomino is colored with the checkerboard coloring. A corner is black if the interior angle lies in a black square, like this:



enter image description here



Here are some examples:



enter image description hereenter image description hereenter image description here



My question is whether it is true that an even polyomino with one hole is always tileable by dominoes.



Background: A related polyomino is called a Temperleyan polyomino (in the same paper), which is formed from an even polyomino by removing one black corner from the outer border, and appending a black cell to each interior border. Here are some examples:



enter image description hereenter image description here



The paper shows (although not really in a way I can follow) Temperleyan polyomino are tileable by dominoes.



It is also easy to show that the deficiency (black minus white cells) in an even polyomino with $H$ holes is $1 - H$, so an even polyomino with 1 hole is balanced (has the same number of black and white cells).



The holes of even polyominoes are also even.





tiling polyomino





share|cite|improve this question












share|cite|improve this question




share|cite|improve this question








edited Aug 1 at 0:46
























asked Jul 30 at 7:01









Herman Tulleken

782416




782416











  • What prevents the 5 by 3 rectangle with a 2 by 1 hole in the centre from being a counterexample? All corner squares are black. but the number of squares is odd so it can't be tiled.
    – orlp
    Aug 1 at 0:34






  • 1




    If you remove the "outer layer" (any cell with a corner touching the outside) from an even polyomino, do you get an even polyomino? And can the "outer layer" be tiled by dominoes (i.e. is it even length)?
    – Solomonoff's Secret
    Aug 1 at 1:19







  • 1




    @Solomonoff'sSecret I found a proof today, and am busy typing it out. It relies basically on the idea you have.
    – Herman Tulleken
    Aug 1 at 1:23






  • 1




    @HermanTulleken Yes, I strongly believe the answer to both my questions are "yes", from which the conclusion follows by induction.
    – Solomonoff's Secret
    Aug 1 at 1:24






  • 1




    My proof is flawed and not easily fixed and yours takes a fundamentally more sound approach.
    – Solomonoff's Secret
    Aug 1 at 2:02
















  • What prevents the 5 by 3 rectangle with a 2 by 1 hole in the centre from being a counterexample? All corner squares are black. but the number of squares is odd so it can't be tiled.
    – orlp
    Aug 1 at 0:34






  • 1




    If you remove the "outer layer" (any cell with a corner touching the outside) from an even polyomino, do you get an even polyomino? And can the "outer layer" be tiled by dominoes (i.e. is it even length)?
    – Solomonoff's Secret
    Aug 1 at 1:19







  • 1




    @Solomonoff'sSecret I found a proof today, and am busy typing it out. It relies basically on the idea you have.
    – Herman Tulleken
    Aug 1 at 1:23






  • 1




    @HermanTulleken Yes, I strongly believe the answer to both my questions are "yes", from which the conclusion follows by induction.
    – Solomonoff's Secret
    Aug 1 at 1:24






  • 1




    My proof is flawed and not easily fixed and yours takes a fundamentally more sound approach.
    – Solomonoff's Secret
    Aug 1 at 2:02















What prevents the 5 by 3 rectangle with a 2 by 1 hole in the centre from being a counterexample? All corner squares are black. but the number of squares is odd so it can't be tiled.
– orlp
Aug 1 at 0:34




What prevents the 5 by 3 rectangle with a 2 by 1 hole in the centre from being a counterexample? All corner squares are black. but the number of squares is odd so it can't be tiled.
– orlp
Aug 1 at 0:34




1




1




If you remove the "outer layer" (any cell with a corner touching the outside) from an even polyomino, do you get an even polyomino? And can the "outer layer" be tiled by dominoes (i.e. is it even length)?
– Solomonoff's Secret
Aug 1 at 1:19





If you remove the "outer layer" (any cell with a corner touching the outside) from an even polyomino, do you get an even polyomino? And can the "outer layer" be tiled by dominoes (i.e. is it even length)?
– Solomonoff's Secret
Aug 1 at 1:19





1




1




@Solomonoff'sSecret I found a proof today, and am busy typing it out. It relies basically on the idea you have.
– Herman Tulleken
Aug 1 at 1:23




@Solomonoff'sSecret I found a proof today, and am busy typing it out. It relies basically on the idea you have.
– Herman Tulleken
Aug 1 at 1:23




1




1




@HermanTulleken Yes, I strongly believe the answer to both my questions are "yes", from which the conclusion follows by induction.
– Solomonoff's Secret
Aug 1 at 1:24




@HermanTulleken Yes, I strongly believe the answer to both my questions are "yes", from which the conclusion follows by induction.
– Solomonoff's Secret
Aug 1 at 1:24




1




1




My proof is flawed and not easily fixed and yours takes a fundamentally more sound approach.
– Solomonoff's Secret
Aug 1 at 2:02




My proof is flawed and not easily fixed and yours takes a fundamentally more sound approach.
– Solomonoff's Secret
Aug 1 at 2:02










2 Answers
2






active

oldest

votes

















up vote
1
down vote













It is true! An even polyomino with one hole is tileable by dominoes.



The proof below has a few sketchy elements; a proof without those will be nice.



Proof. For this proof to work, we will manipulate the border (either the outside or inside border) to give a new polyomino with a hole, and we will consider regions where borders overlap also valid polyominoes, and they are even if the corners are black as with the regular definition. Here are some examples of such polyominoes (the outside border has been slightly displaced where it coincides with the inside border).



enter image description here



Here, tileable means tileable by dominoes.



  1. A ring is a polyomino where each cell has exactly two borders. All rings are tileable.


  2. A peak is a cell with exactly one neighbor. In an even polyomino, all peaks must be black (otherwise there are white corners). Also, all black peaks must be attached to a white cell with exactly two neighbors. Therefor, in an even polyomino, if we move the border to exclude the peak and it's neighboring cell, we are still left with an even polyomino.


An example of this manipulation:



enter image description here



  1. A $2 times 2$ square can be of two types. Type I has a black square in the top right, a Type II square has a black square in the top left. If a Type I square occurs in a corner of the polyomino, we can move the border to exclude it, and keep the polyomino even.

An example of this manipulation:



enter image description here



  1. All convex corners of a even polyomino are one of these four types:

enter image description here



(This part is a bit sketchy; it requires considering many cases.)



  1. If we perform the manipulations in 2 and 3 until we cannot, we are only left with the following types of convex corners:

enter image description here



  1. A figure with only type 3 and 4 convex corners and one hole cannot contain a $2times2$ subfigure.

Suppose there is such a square. Find the largest connected set of cells that contains this square such that each cell is part of a $2times 2$ subfigure. This set of cells must have at least four convex corners (as do all rectilinear figures). For these corners to not be corners of the entire figure, each needs to be "covered" by a "strand" (the picture below shows a possibility.) These strands must either result in peaks, or they must connect in pairs. If they connect in pairs, there are two holes, and this is impossible. Therefor, there cannot be any $2times 2$ subfigure.



enter image description here



In this^ image, there is a $2 times 2$ square, contained in a $3times 3$ square where each corner is covered by a white cell that stars the strand. In this example, the strands connect in pairs, leading to two holes.



  1. We cannot have any X or T junctions in a figure with no $2times2$ subfigures, no peaks, and one hole.

Suppose we have an X junction. Each of the four connectors must eventually lead to a peak, or pairs of them must join. In the latter case, we have two holes, which is impossible. Therefor there are no X junctions.



Suppose we have a T-junction. Each of the three connectors must either lead to a peak, or they must join other connectors. We can only join up if we have at least another T junction, in which case we will have at least have two holes, which is impossible. Therefor there are no T junctions.



  1. This means we either have a ring, or a polyomino with no area (thus the inner and outer border coincide completely).

(This is also sketchy, and require cases to make sure we cannot have other possibilities.)



  1. This procedure shows we can partition any even polyomino with one hole into a set with $dominoes$, $2times2$ squares, and either a ring or empty polyomino. All the elements of this partition are tileable, and therefor, so is the whole figure.

Some remarks:



  • The double border definition is necessary to deal with polyominoes such as this below. If we did not have that, removing a $2times 2$ corner would not leave an even polyomino. (It would be nice to find a proof that does not require this trick.)

enter image description here



  • An algorithm follows immediately from the border manipulations.





share|cite|improve this answer























  • Regarding step 4, what about + or T corners?
    – Solomonoff's Secret
    Aug 1 at 2:01











  • Hmmmm yes this is a problem. Although it can be resolved I think. I will add those cases. (Lol maybe this proof is broken after all.)
    – Herman Tulleken
    Aug 1 at 2:05











  • @Solomonoff'sSecret I edited and expanded the proof to address the issues you raised. (Note, the four corners of step 4 has been changed to 4 convex corners. and parts have been added to show these junctions cannot exist after we did all manipulations in 2 and 3.)
    – Herman Tulleken
    Aug 1 at 17:29

















up vote
0
down vote













This answer is an outline. However I believe it covers all cases.



Call a polyomino with the same number of black and white cells and no hole type 1. Call an even polyomino with one hole type 2.



First note that a type 1 polyomino can be tiled. This is because either it is empty or there is a corner on which we can place a domino such that the remaining cells are type 1.



Now we prove that a type 2 polyomino can be tiled by induction on its size. Consider the graph whose vertices are the cells of and in the hole of the polyomino and whose edges go between cells sharing a side.



  • If the graph has a cut vertex then it has a white cut vertex $v$. Cut the polyomino on whichever side of $v$ leaves $v$ on the side away from the hole. The result is one type 1 polyomino on the side with $v$, as it has one white corner and no hole, and one smaller type 2 polyomino on the other side.

  • If the graph has no cut vertex then the set of vertices with at least one corner touching the outside (unbounded region) consists of a finite number of even length straight segments, each going from one corner (inclusive) to another (exclusive), none of which overlap. These segments can be tiled and removed, leaving a smaller polyomino. If this smaller polyomino still has a hole then it is type 2. If not, it is type 1 as it has the same number of white and black cells.

In both cases each smaller polyomino can be tiled.






share|cite|improve this answer





















  • Are there additional constraints on type 1 polies? (for example xxx/0×0/0x0/xxx is not tileable (x is cell, 0 is space, / is newline))
    – Herman Tulleken
    Aug 1 at 5:22










  • See Thurston's height condition for a necessary condition for tileability. His paper Conway's tiling groups gives more details and a necessary and sufficient condition.
    – Grant B.
    Aug 1 at 7:34











  • @HermanTulleken Good catch. I will revisit.
    – Solomonoff's Secret
    Aug 1 at 12:01










Your Answer




StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);








 

draft saved


draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2866719%2fis-every-even-polyomino-with-one-hole-tileable-by-dominoes%23new-answer', 'question_page');

);

Post as a guest

















2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
1
down vote













It is true! An even polyomino with one hole is tileable by dominoes.



The proof below has a few sketchy elements; a proof without those will be nice.



Proof. For this proof to work, we will manipulate the border (either the outside or inside border) to give a new polyomino with a hole, and we will consider regions where borders overlap also valid polyominoes, and they are even if the corners are black as with the regular definition. Here are some examples of such polyominoes (the outside border has been slightly displaced where it coincides with the inside border).



enter image description here



Here, tileable means tileable by dominoes.



  1. A ring is a polyomino where each cell has exactly two borders. All rings are tileable.


  2. A peak is a cell with exactly one neighbor. In an even polyomino, all peaks must be black (otherwise there are white corners). Also, all black peaks must be attached to a white cell with exactly two neighbors. Therefor, in an even polyomino, if we move the border to exclude the peak and it's neighboring cell, we are still left with an even polyomino.


An example of this manipulation:



enter image description here



  1. A $2 times 2$ square can be of two types. Type I has a black square in the top right, a Type II square has a black square in the top left. If a Type I square occurs in a corner of the polyomino, we can move the border to exclude it, and keep the polyomino even.

An example of this manipulation:



enter image description here



  1. All convex corners of a even polyomino are one of these four types:

enter image description here



(This part is a bit sketchy; it requires considering many cases.)



  1. If we perform the manipulations in 2 and 3 until we cannot, we are only left with the following types of convex corners:

enter image description here



  1. A figure with only type 3 and 4 convex corners and one hole cannot contain a $2times2$ subfigure.

Suppose there is such a square. Find the largest connected set of cells that contains this square such that each cell is part of a $2times 2$ subfigure. This set of cells must have at least four convex corners (as do all rectilinear figures). For these corners to not be corners of the entire figure, each needs to be "covered" by a "strand" (the picture below shows a possibility.) These strands must either result in peaks, or they must connect in pairs. If they connect in pairs, there are two holes, and this is impossible. Therefor, there cannot be any $2times 2$ subfigure.



enter image description here



In this^ image, there is a $2 times 2$ square, contained in a $3times 3$ square where each corner is covered by a white cell that stars the strand. In this example, the strands connect in pairs, leading to two holes.



  1. We cannot have any X or T junctions in a figure with no $2times2$ subfigures, no peaks, and one hole.

Suppose we have an X junction. Each of the four connectors must eventually lead to a peak, or pairs of them must join. In the latter case, we have two holes, which is impossible. Therefor there are no X junctions.



Suppose we have a T-junction. Each of the three connectors must either lead to a peak, or they must join other connectors. We can only join up if we have at least another T junction, in which case we will have at least have two holes, which is impossible. Therefor there are no T junctions.



  1. This means we either have a ring, or a polyomino with no area (thus the inner and outer border coincide completely).

(This is also sketchy, and require cases to make sure we cannot have other possibilities.)



  1. This procedure shows we can partition any even polyomino with one hole into a set with $dominoes$, $2times2$ squares, and either a ring or empty polyomino. All the elements of this partition are tileable, and therefor, so is the whole figure.

Some remarks:



  • The double border definition is necessary to deal with polyominoes such as this below. If we did not have that, removing a $2times 2$ corner would not leave an even polyomino. (It would be nice to find a proof that does not require this trick.)

enter image description here



  • An algorithm follows immediately from the border manipulations.





share|cite|improve this answer























  • Regarding step 4, what about + or T corners?
    – Solomonoff's Secret
    Aug 1 at 2:01











  • Hmmmm yes this is a problem. Although it can be resolved I think. I will add those cases. (Lol maybe this proof is broken after all.)
    – Herman Tulleken
    Aug 1 at 2:05











  • @Solomonoff'sSecret I edited and expanded the proof to address the issues you raised. (Note, the four corners of step 4 has been changed to 4 convex corners. and parts have been added to show these junctions cannot exist after we did all manipulations in 2 and 3.)
    – Herman Tulleken
    Aug 1 at 17:29














up vote
1
down vote













It is true! An even polyomino with one hole is tileable by dominoes.



The proof below has a few sketchy elements; a proof without those will be nice.



Proof. For this proof to work, we will manipulate the border (either the outside or inside border) to give a new polyomino with a hole, and we will consider regions where borders overlap also valid polyominoes, and they are even if the corners are black as with the regular definition. Here are some examples of such polyominoes (the outside border has been slightly displaced where it coincides with the inside border).



enter image description here



Here, tileable means tileable by dominoes.



  1. A ring is a polyomino where each cell has exactly two borders. All rings are tileable.


  2. A peak is a cell with exactly one neighbor. In an even polyomino, all peaks must be black (otherwise there are white corners). Also, all black peaks must be attached to a white cell with exactly two neighbors. Therefor, in an even polyomino, if we move the border to exclude the peak and it's neighboring cell, we are still left with an even polyomino.


An example of this manipulation:



enter image description here



  1. A $2 times 2$ square can be of two types. Type I has a black square in the top right, a Type II square has a black square in the top left. If a Type I square occurs in a corner of the polyomino, we can move the border to exclude it, and keep the polyomino even.

An example of this manipulation:



enter image description here



  1. All convex corners of a even polyomino are one of these four types:

enter image description here



(This part is a bit sketchy; it requires considering many cases.)



  1. If we perform the manipulations in 2 and 3 until we cannot, we are only left with the following types of convex corners:

enter image description here



  1. A figure with only type 3 and 4 convex corners and one hole cannot contain a $2times2$ subfigure.

Suppose there is such a square. Find the largest connected set of cells that contains this square such that each cell is part of a $2times 2$ subfigure. This set of cells must have at least four convex corners (as do all rectilinear figures). For these corners to not be corners of the entire figure, each needs to be "covered" by a "strand" (the picture below shows a possibility.) These strands must either result in peaks, or they must connect in pairs. If they connect in pairs, there are two holes, and this is impossible. Therefor, there cannot be any $2times 2$ subfigure.



enter image description here



In this^ image, there is a $2 times 2$ square, contained in a $3times 3$ square where each corner is covered by a white cell that stars the strand. In this example, the strands connect in pairs, leading to two holes.



  1. We cannot have any X or T junctions in a figure with no $2times2$ subfigures, no peaks, and one hole.

Suppose we have an X junction. Each of the four connectors must eventually lead to a peak, or pairs of them must join. In the latter case, we have two holes, which is impossible. Therefor there are no X junctions.



Suppose we have a T-junction. Each of the three connectors must either lead to a peak, or they must join other connectors. We can only join up if we have at least another T junction, in which case we will have at least have two holes, which is impossible. Therefor there are no T junctions.



  1. This means we either have a ring, or a polyomino with no area (thus the inner and outer border coincide completely).

(This is also sketchy, and require cases to make sure we cannot have other possibilities.)



  1. This procedure shows we can partition any even polyomino with one hole into a set with $dominoes$, $2times2$ squares, and either a ring or empty polyomino. All the elements of this partition are tileable, and therefor, so is the whole figure.

Some remarks:



  • The double border definition is necessary to deal with polyominoes such as this below. If we did not have that, removing a $2times 2$ corner would not leave an even polyomino. (It would be nice to find a proof that does not require this trick.)

enter image description here



  • An algorithm follows immediately from the border manipulations.





share|cite|improve this answer























  • Regarding step 4, what about + or T corners?
    – Solomonoff's Secret
    Aug 1 at 2:01











  • Hmmmm yes this is a problem. Although it can be resolved I think. I will add those cases. (Lol maybe this proof is broken after all.)
    – Herman Tulleken
    Aug 1 at 2:05











  • @Solomonoff'sSecret I edited and expanded the proof to address the issues you raised. (Note, the four corners of step 4 has been changed to 4 convex corners. and parts have been added to show these junctions cannot exist after we did all manipulations in 2 and 3.)
    – Herman Tulleken
    Aug 1 at 17:29












up vote
1
down vote










up vote
1
down vote









It is true! An even polyomino with one hole is tileable by dominoes.



The proof below has a few sketchy elements; a proof without those will be nice.



Proof. For this proof to work, we will manipulate the border (either the outside or inside border) to give a new polyomino with a hole, and we will consider regions where borders overlap also valid polyominoes, and they are even if the corners are black as with the regular definition. Here are some examples of such polyominoes (the outside border has been slightly displaced where it coincides with the inside border).



enter image description here



Here, tileable means tileable by dominoes.



  1. A ring is a polyomino where each cell has exactly two borders. All rings are tileable.


  2. A peak is a cell with exactly one neighbor. In an even polyomino, all peaks must be black (otherwise there are white corners). Also, all black peaks must be attached to a white cell with exactly two neighbors. Therefor, in an even polyomino, if we move the border to exclude the peak and it's neighboring cell, we are still left with an even polyomino.


An example of this manipulation:



enter image description here



  1. A $2 times 2$ square can be of two types. Type I has a black square in the top right, a Type II square has a black square in the top left. If a Type I square occurs in a corner of the polyomino, we can move the border to exclude it, and keep the polyomino even.

An example of this manipulation:



enter image description here



  1. All convex corners of a even polyomino are one of these four types:

enter image description here



(This part is a bit sketchy; it requires considering many cases.)



  1. If we perform the manipulations in 2 and 3 until we cannot, we are only left with the following types of convex corners:

enter image description here



  1. A figure with only type 3 and 4 convex corners and one hole cannot contain a $2times2$ subfigure.

Suppose there is such a square. Find the largest connected set of cells that contains this square such that each cell is part of a $2times 2$ subfigure. This set of cells must have at least four convex corners (as do all rectilinear figures). For these corners to not be corners of the entire figure, each needs to be "covered" by a "strand" (the picture below shows a possibility.) These strands must either result in peaks, or they must connect in pairs. If they connect in pairs, there are two holes, and this is impossible. Therefor, there cannot be any $2times 2$ subfigure.



enter image description here



In this^ image, there is a $2 times 2$ square, contained in a $3times 3$ square where each corner is covered by a white cell that stars the strand. In this example, the strands connect in pairs, leading to two holes.



  1. We cannot have any X or T junctions in a figure with no $2times2$ subfigures, no peaks, and one hole.

Suppose we have an X junction. Each of the four connectors must eventually lead to a peak, or pairs of them must join. In the latter case, we have two holes, which is impossible. Therefor there are no X junctions.



Suppose we have a T-junction. Each of the three connectors must either lead to a peak, or they must join other connectors. We can only join up if we have at least another T junction, in which case we will have at least have two holes, which is impossible. Therefor there are no T junctions.



  1. This means we either have a ring, or a polyomino with no area (thus the inner and outer border coincide completely).

(This is also sketchy, and require cases to make sure we cannot have other possibilities.)



  1. This procedure shows we can partition any even polyomino with one hole into a set with $dominoes$, $2times2$ squares, and either a ring or empty polyomino. All the elements of this partition are tileable, and therefor, so is the whole figure.

Some remarks:



  • The double border definition is necessary to deal with polyominoes such as this below. If we did not have that, removing a $2times 2$ corner would not leave an even polyomino. (It would be nice to find a proof that does not require this trick.)

enter image description here



  • An algorithm follows immediately from the border manipulations.





share|cite|improve this answer















It is true! An even polyomino with one hole is tileable by dominoes.



The proof below has a few sketchy elements; a proof without those will be nice.



Proof. For this proof to work, we will manipulate the border (either the outside or inside border) to give a new polyomino with a hole, and we will consider regions where borders overlap also valid polyominoes, and they are even if the corners are black as with the regular definition. Here are some examples of such polyominoes (the outside border has been slightly displaced where it coincides with the inside border).



enter image description here



Here, tileable means tileable by dominoes.



  1. A ring is a polyomino where each cell has exactly two borders. All rings are tileable.


  2. A peak is a cell with exactly one neighbor. In an even polyomino, all peaks must be black (otherwise there are white corners). Also, all black peaks must be attached to a white cell with exactly two neighbors. Therefor, in an even polyomino, if we move the border to exclude the peak and it's neighboring cell, we are still left with an even polyomino.


An example of this manipulation:



enter image description here



  1. A $2 times 2$ square can be of two types. Type I has a black square in the top right, a Type II square has a black square in the top left. If a Type I square occurs in a corner of the polyomino, we can move the border to exclude it, and keep the polyomino even.

An example of this manipulation:



enter image description here



  1. All convex corners of a even polyomino are one of these four types:

enter image description here



(This part is a bit sketchy; it requires considering many cases.)



  1. If we perform the manipulations in 2 and 3 until we cannot, we are only left with the following types of convex corners:

enter image description here



  1. A figure with only type 3 and 4 convex corners and one hole cannot contain a $2times2$ subfigure.

Suppose there is such a square. Find the largest connected set of cells that contains this square such that each cell is part of a $2times 2$ subfigure. This set of cells must have at least four convex corners (as do all rectilinear figures). For these corners to not be corners of the entire figure, each needs to be "covered" by a "strand" (the picture below shows a possibility.) These strands must either result in peaks, or they must connect in pairs. If they connect in pairs, there are two holes, and this is impossible. Therefor, there cannot be any $2times 2$ subfigure.



enter image description here



In this^ image, there is a $2 times 2$ square, contained in a $3times 3$ square where each corner is covered by a white cell that stars the strand. In this example, the strands connect in pairs, leading to two holes.



  1. We cannot have any X or T junctions in a figure with no $2times2$ subfigures, no peaks, and one hole.

Suppose we have an X junction. Each of the four connectors must eventually lead to a peak, or pairs of them must join. In the latter case, we have two holes, which is impossible. Therefor there are no X junctions.



Suppose we have a T-junction. Each of the three connectors must either lead to a peak, or they must join other connectors. We can only join up if we have at least another T junction, in which case we will have at least have two holes, which is impossible. Therefor there are no T junctions.



  1. This means we either have a ring, or a polyomino with no area (thus the inner and outer border coincide completely).

(This is also sketchy, and require cases to make sure we cannot have other possibilities.)



  1. This procedure shows we can partition any even polyomino with one hole into a set with $dominoes$, $2times2$ squares, and either a ring or empty polyomino. All the elements of this partition are tileable, and therefor, so is the whole figure.

Some remarks:



  • The double border definition is necessary to deal with polyominoes such as this below. If we did not have that, removing a $2times 2$ corner would not leave an even polyomino. (It would be nice to find a proof that does not require this trick.)

enter image description here



  • An algorithm follows immediately from the border manipulations.






share|cite|improve this answer















share|cite|improve this answer



share|cite|improve this answer








edited Aug 1 at 17:24


























answered Aug 1 at 1:49









Herman Tulleken

782416




782416











  • Regarding step 4, what about + or T corners?
    – Solomonoff's Secret
    Aug 1 at 2:01











  • Hmmmm yes this is a problem. Although it can be resolved I think. I will add those cases. (Lol maybe this proof is broken after all.)
    – Herman Tulleken
    Aug 1 at 2:05











  • @Solomonoff'sSecret I edited and expanded the proof to address the issues you raised. (Note, the four corners of step 4 has been changed to 4 convex corners. and parts have been added to show these junctions cannot exist after we did all manipulations in 2 and 3.)
    – Herman Tulleken
    Aug 1 at 17:29
















  • Regarding step 4, what about + or T corners?
    – Solomonoff's Secret
    Aug 1 at 2:01











  • Hmmmm yes this is a problem. Although it can be resolved I think. I will add those cases. (Lol maybe this proof is broken after all.)
    – Herman Tulleken
    Aug 1 at 2:05











  • @Solomonoff'sSecret I edited and expanded the proof to address the issues you raised. (Note, the four corners of step 4 has been changed to 4 convex corners. and parts have been added to show these junctions cannot exist after we did all manipulations in 2 and 3.)
    – Herman Tulleken
    Aug 1 at 17:29















Regarding step 4, what about + or T corners?
– Solomonoff's Secret
Aug 1 at 2:01





Regarding step 4, what about + or T corners?
– Solomonoff's Secret
Aug 1 at 2:01













Hmmmm yes this is a problem. Although it can be resolved I think. I will add those cases. (Lol maybe this proof is broken after all.)
– Herman Tulleken
Aug 1 at 2:05





Hmmmm yes this is a problem. Although it can be resolved I think. I will add those cases. (Lol maybe this proof is broken after all.)
– Herman Tulleken
Aug 1 at 2:05













@Solomonoff'sSecret I edited and expanded the proof to address the issues you raised. (Note, the four corners of step 4 has been changed to 4 convex corners. and parts have been added to show these junctions cannot exist after we did all manipulations in 2 and 3.)
– Herman Tulleken
Aug 1 at 17:29




@Solomonoff'sSecret I edited and expanded the proof to address the issues you raised. (Note, the four corners of step 4 has been changed to 4 convex corners. and parts have been added to show these junctions cannot exist after we did all manipulations in 2 and 3.)
– Herman Tulleken
Aug 1 at 17:29










up vote
0
down vote













This answer is an outline. However I believe it covers all cases.



Call a polyomino with the same number of black and white cells and no hole type 1. Call an even polyomino with one hole type 2.



First note that a type 1 polyomino can be tiled. This is because either it is empty or there is a corner on which we can place a domino such that the remaining cells are type 1.



Now we prove that a type 2 polyomino can be tiled by induction on its size. Consider the graph whose vertices are the cells of and in the hole of the polyomino and whose edges go between cells sharing a side.



  • If the graph has a cut vertex then it has a white cut vertex $v$. Cut the polyomino on whichever side of $v$ leaves $v$ on the side away from the hole. The result is one type 1 polyomino on the side with $v$, as it has one white corner and no hole, and one smaller type 2 polyomino on the other side.

  • If the graph has no cut vertex then the set of vertices with at least one corner touching the outside (unbounded region) consists of a finite number of even length straight segments, each going from one corner (inclusive) to another (exclusive), none of which overlap. These segments can be tiled and removed, leaving a smaller polyomino. If this smaller polyomino still has a hole then it is type 2. If not, it is type 1 as it has the same number of white and black cells.

In both cases each smaller polyomino can be tiled.






share|cite|improve this answer





















  • Are there additional constraints on type 1 polies? (for example xxx/0×0/0x0/xxx is not tileable (x is cell, 0 is space, / is newline))
    – Herman Tulleken
    Aug 1 at 5:22










  • See Thurston's height condition for a necessary condition for tileability. His paper Conway's tiling groups gives more details and a necessary and sufficient condition.
    – Grant B.
    Aug 1 at 7:34











  • @HermanTulleken Good catch. I will revisit.
    – Solomonoff's Secret
    Aug 1 at 12:01














up vote
0
down vote













This answer is an outline. However I believe it covers all cases.



Call a polyomino with the same number of black and white cells and no hole type 1. Call an even polyomino with one hole type 2.



First note that a type 1 polyomino can be tiled. This is because either it is empty or there is a corner on which we can place a domino such that the remaining cells are type 1.



Now we prove that a type 2 polyomino can be tiled by induction on its size. Consider the graph whose vertices are the cells of and in the hole of the polyomino and whose edges go between cells sharing a side.



  • If the graph has a cut vertex then it has a white cut vertex $v$. Cut the polyomino on whichever side of $v$ leaves $v$ on the side away from the hole. The result is one type 1 polyomino on the side with $v$, as it has one white corner and no hole, and one smaller type 2 polyomino on the other side.

  • If the graph has no cut vertex then the set of vertices with at least one corner touching the outside (unbounded region) consists of a finite number of even length straight segments, each going from one corner (inclusive) to another (exclusive), none of which overlap. These segments can be tiled and removed, leaving a smaller polyomino. If this smaller polyomino still has a hole then it is type 2. If not, it is type 1 as it has the same number of white and black cells.

In both cases each smaller polyomino can be tiled.






share|cite|improve this answer





















  • Are there additional constraints on type 1 polies? (for example xxx/0×0/0x0/xxx is not tileable (x is cell, 0 is space, / is newline))
    – Herman Tulleken
    Aug 1 at 5:22










  • See Thurston's height condition for a necessary condition for tileability. His paper Conway's tiling groups gives more details and a necessary and sufficient condition.
    – Grant B.
    Aug 1 at 7:34











  • @HermanTulleken Good catch. I will revisit.
    – Solomonoff's Secret
    Aug 1 at 12:01












up vote
0
down vote










up vote
0
down vote









This answer is an outline. However I believe it covers all cases.



Call a polyomino with the same number of black and white cells and no hole type 1. Call an even polyomino with one hole type 2.



First note that a type 1 polyomino can be tiled. This is because either it is empty or there is a corner on which we can place a domino such that the remaining cells are type 1.



Now we prove that a type 2 polyomino can be tiled by induction on its size. Consider the graph whose vertices are the cells of and in the hole of the polyomino and whose edges go between cells sharing a side.



  • If the graph has a cut vertex then it has a white cut vertex $v$. Cut the polyomino on whichever side of $v$ leaves $v$ on the side away from the hole. The result is one type 1 polyomino on the side with $v$, as it has one white corner and no hole, and one smaller type 2 polyomino on the other side.

  • If the graph has no cut vertex then the set of vertices with at least one corner touching the outside (unbounded region) consists of a finite number of even length straight segments, each going from one corner (inclusive) to another (exclusive), none of which overlap. These segments can be tiled and removed, leaving a smaller polyomino. If this smaller polyomino still has a hole then it is type 2. If not, it is type 1 as it has the same number of white and black cells.

In both cases each smaller polyomino can be tiled.






share|cite|improve this answer













This answer is an outline. However I believe it covers all cases.



Call a polyomino with the same number of black and white cells and no hole type 1. Call an even polyomino with one hole type 2.



First note that a type 1 polyomino can be tiled. This is because either it is empty or there is a corner on which we can place a domino such that the remaining cells are type 1.



Now we prove that a type 2 polyomino can be tiled by induction on its size. Consider the graph whose vertices are the cells of and in the hole of the polyomino and whose edges go between cells sharing a side.



  • If the graph has a cut vertex then it has a white cut vertex $v$. Cut the polyomino on whichever side of $v$ leaves $v$ on the side away from the hole. The result is one type 1 polyomino on the side with $v$, as it has one white corner and no hole, and one smaller type 2 polyomino on the other side.

  • If the graph has no cut vertex then the set of vertices with at least one corner touching the outside (unbounded region) consists of a finite number of even length straight segments, each going from one corner (inclusive) to another (exclusive), none of which overlap. These segments can be tiled and removed, leaving a smaller polyomino. If this smaller polyomino still has a hole then it is type 2. If not, it is type 1 as it has the same number of white and black cells.

In both cases each smaller polyomino can be tiled.







share|cite|improve this answer













share|cite|improve this answer



share|cite|improve this answer











answered Aug 1 at 4:20









Solomonoff's Secret

3,53311132




3,53311132











  • Are there additional constraints on type 1 polies? (for example xxx/0×0/0x0/xxx is not tileable (x is cell, 0 is space, / is newline))
    – Herman Tulleken
    Aug 1 at 5:22










  • See Thurston's height condition for a necessary condition for tileability. His paper Conway's tiling groups gives more details and a necessary and sufficient condition.
    – Grant B.
    Aug 1 at 7:34











  • @HermanTulleken Good catch. I will revisit.
    – Solomonoff's Secret
    Aug 1 at 12:01
















  • Are there additional constraints on type 1 polies? (for example xxx/0×0/0x0/xxx is not tileable (x is cell, 0 is space, / is newline))
    – Herman Tulleken
    Aug 1 at 5:22










  • See Thurston's height condition for a necessary condition for tileability. His paper Conway's tiling groups gives more details and a necessary and sufficient condition.
    – Grant B.
    Aug 1 at 7:34











  • @HermanTulleken Good catch. I will revisit.
    – Solomonoff's Secret
    Aug 1 at 12:01















Are there additional constraints on type 1 polies? (for example xxx/0×0/0x0/xxx is not tileable (x is cell, 0 is space, / is newline))
– Herman Tulleken
Aug 1 at 5:22




Are there additional constraints on type 1 polies? (for example xxx/0×0/0x0/xxx is not tileable (x is cell, 0 is space, / is newline))
– Herman Tulleken
Aug 1 at 5:22












See Thurston's height condition for a necessary condition for tileability. His paper Conway's tiling groups gives more details and a necessary and sufficient condition.
– Grant B.
Aug 1 at 7:34





See Thurston's height condition for a necessary condition for tileability. His paper Conway's tiling groups gives more details and a necessary and sufficient condition.
– Grant B.
Aug 1 at 7:34













@HermanTulleken Good catch. I will revisit.
– Solomonoff's Secret
Aug 1 at 12:01




@HermanTulleken Good catch. I will revisit.
– Solomonoff's Secret
Aug 1 at 12:01












 

draft saved


draft discarded


























 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2866719%2fis-every-even-polyomino-with-one-hole-tileable-by-dominoes%23new-answer', 'question_page');

);

Post as a guest
































































Comments

Post a Comment

Popular posts from this blog

What is the equation of a 3D cone with generalised tilt?

Image
Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite What is the equation of a 3D cone with generalized tilt? I've noticed that in most equations given to represent a cone, there is no parameter which defines the tilt of the cone in 3D space and that most of them have their point at the origin $(0,0,0)$ - I was wondering if anyone could give me a more generalized cone equation for a cone in any position in 3D space 3d share | cite | improve this question edited Jul 25 '16 at 0:05 ervx 9,425 3 13 36 asked Jul 24 '16 at 15:38 Charlene 11 2 2 Welcome to Math.SE! Could you please explain a few things to help people give an answer useful to you: 1. What do you mean by "generalized tilt"? 2. Are you asking about a right circular cone? Does the angle at the vertex matter? 3. What form of answer (implicit, parametric...?) are you looking for? 4. If this is homework, what tools do you have available, an
Read more

Color the edges and diagonals of a regular polygon

Image
Clash Royale CLAN TAG #URR8PPP up vote 5 down vote favorite 1 Here is the problem: For what $n$ is it possible to color the edges and diagonals of an $n$-side regular polygon with $dfracbinomn23$ colors, such that you use every color exactly three times and for every color the three segments (edges or diagonals) with that color form a triangle? Trivially $nequiv 0 text or 1 pmod3$. I can also prove that if the statement is true for $k$ than it is true for $3k$ as well. How to finish? Please help! Thanks combinatorial-geometry share | cite | improve this question edited Aug 6 at 21:57 alcana 118 4 asked Aug 6 at 21:15 Leo Gardner 356 11 Even assuming "polyhpn" in the title is a typo for polygon , it is unclear what you mean by "the edges and sides". Aren't the side of a regular polygon the same as the edges? A regular $n$-sided polygon has $n$ edges. – hardmath Aug 6 at 21:20 3 $n$ ne
Read more

Relationship between determinant of matrix and determinant of adjoint?

Image
Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite We are studying adjoints in class, and I was curious if there is a relationship between the determinant of matrix A, and the determinant of the adjoint of matrix A? I assume there would be a relationship because finding the adjoint requires creating a cofactor matrix and then transposing it. linear-algebra determinant adjoint-operators share | cite | improve this question asked Nov 17 '17 at 17:32 CluelessCoder 32 5 For a square matrix $A$ of order $n$, we have $A(operatornameadj A)=(operatornameadj A)A=|A|I_n$ where $I_n$ is the identity matrix of order $n$. This should tell you about the determinant of the adjoint in terms of that of $A$ (use multiplicative property and other elementary properties of determinants). – Prasun Biswas Nov 17 '17 at 17:35 1 @CluelessCoder: see here: math.stackexchange.com/questions/516127/… – Hector Blandin Nov 17 &
Read more