Mixing
Domino Tiling 8 x 8 grid proof
Clash Royale CLAN TAG#URR8PPP
up vote
8
down vote
favorite
How can I prove that at least 8 dominoes are required to allow a placement to which no further domino can be added without two dominoes sharing an edge
Any help will be appreciated.
edit : For 9 * 9 grid this is the best solution :
combinatorics graph-theory chessboard
asked Jul 19 at 6:04
Rumi
615
 |Â
show 7 more comments
up vote
8
down vote
favorite
How can I prove that at least 8 dominoes are required to allow a placement to which no further domino can be added without two dominoes sharing an edge
Any help will be appreciated.
edit : For 9 * 9 grid this is the best solution :
combinatorics graph-theory chessboard
asked Jul 19 at 6:04
Rumi
615
I suggest reformulating the question as "How can I prove that on an $8$ x $8$ grid, 8 is the maximum number of dominoes I can place such that no two dominoes share an edge?". In the current formulation, the requirement that the first $8$ dominoes don't share an edge is missing; the claim would be trivially wrong if taken literally.
– joriki
Jul 19 at 6:09
2
@JyrkiLahtonen You could easily place 16 dominoes in an admissible configuration.
– Parcly Taxel
Jul 19 at 6:10
4
A wild guess: Perhaps one might prove that at least $8$ dominoes are required to allow a placement to which no further domino can be added without two dominoes sharing an edge? Aha -- your new comment above seems to suggest that this is indeed what you had in mind. Then my suggestion above was the wrong clarification of the original question.
– joriki
Jul 19 at 6:14
1
I think the wording of the question needs to be changed, otherwise 8 isn't the answer. Seems Joriki's last comment might be the right wording.
– coffeemath
Jul 19 at 6:17
1
@LoveInvariants on zero you have empty spaces where you can add an domino without it sharing an edge. Similarly this is the case up till 7 where no placement exists such as the one in the picture where adding another domino is impossible without it sharing an edge with the other.
– Rumi
Jul 19 at 6:23
 |Â
show 7 more comments
up vote
8
down vote
favorite
up vote
8
down vote
favorite
How can I prove that at least 8 dominoes are required to allow a placement to which no further domino can be added without two dominoes sharing an edge
Any help will be appreciated.
edit : For 9 * 9 grid this is the best solution :
combinatorics graph-theory chessboard
asked Jul 19 at 6:04
Rumi
615
How can I prove that at least 8 dominoes are required to allow a placement to which no further domino can be added without two dominoes sharing an edge
Any help will be appreciated.
edit : For 9 * 9 grid this is the best solution :
combinatorics graph-theory chessboard
asked Jul 19 at 6:04
Rumi
615
edited Jul 19 at 8:32
asked Jul 19 at 6:04
Rumi
615
asked Jul 19 at 6:04
Rumi
615
asked Jul 19 at 6:04
Rumi
615
615
I suggest reformulating the question as "How can I prove that on an $8$ x $8$ grid, 8 is the maximum number of dominoes I can place such that no two dominoes share an edge?". In the current formulation, the requirement that the first $8$ dominoes don't share an edge is missing; the claim would be trivially wrong if taken literally.
– joriki
Jul 19 at 6:09
2
@JyrkiLahtonen You could easily place 16 dominoes in an admissible configuration.
– Parcly Taxel
Jul 19 at 6:10
4
A wild guess: Perhaps one might prove that at least $8$ dominoes are required to allow a placement to which no further domino can be added without two dominoes sharing an edge? Aha -- your new comment above seems to suggest that this is indeed what you had in mind. Then my suggestion above was the wrong clarification of the original question.
– joriki
Jul 19 at 6:14
1
I think the wording of the question needs to be changed, otherwise 8 isn't the answer. Seems Joriki's last comment might be the right wording.
– coffeemath
Jul 19 at 6:17
1
@LoveInvariants on zero you have empty spaces where you can add an domino without it sharing an edge. Similarly this is the case up till 7 where no placement exists such as the one in the picture where adding another domino is impossible without it sharing an edge with the other.
– Rumi
Jul 19 at 6:23
 |Â
show 7 more comments
I suggest reformulating the question as "How can I prove that on an $8$ x $8$ grid, 8 is the maximum number of dominoes I can place such that no two dominoes share an edge?". In the current formulation, the requirement that the first $8$ dominoes don't share an edge is missing; the claim would be trivially wrong if taken literally.
– joriki
Jul 19 at 6:09
2
@JyrkiLahtonen You could easily place 16 dominoes in an admissible configuration.
– Parcly Taxel
Jul 19 at 6:10
4
A wild guess: Perhaps one might prove that at least $8$ dominoes are required to allow a placement to which no further domino can be added without two dominoes sharing an edge? Aha -- your new comment above seems to suggest that this is indeed what you had in mind. Then my suggestion above was the wrong clarification of the original question.
– joriki
Jul 19 at 6:14
1
I think the wording of the question needs to be changed, otherwise 8 isn't the answer. Seems Joriki's last comment might be the right wording.
– coffeemath
Jul 19 at 6:17
1
@LoveInvariants on zero you have empty spaces where you can add an domino without it sharing an edge. Similarly this is the case up till 7 where no placement exists such as the one in the picture where adding another domino is impossible without it sharing an edge with the other.
– Rumi
Jul 19 at 6:23
I suggest reformulating the question as "How can I prove that on an $8$ x $8$ grid, 8 is the maximum number of dominoes I can place such that no two dominoes share an edge?". In the current formulation, the requirement that the first $8$ dominoes don't share an edge is missing; the claim would be trivially wrong if taken literally.
– joriki
Jul 19 at 6:09
I suggest reformulating the question as "How can I prove that on an $8$ x $8$ grid, 8 is the maximum number of dominoes I can place such that no two dominoes share an edge?". In the current formulation, the requirement that the first $8$ dominoes don't share an edge is missing; the claim would be trivially wrong if taken literally.
– joriki
Jul 19 at 6:09
2
2
@JyrkiLahtonen You could easily place 16 dominoes in an admissible configuration.
– Parcly Taxel
Jul 19 at 6:10
@JyrkiLahtonen You could easily place 16 dominoes in an admissible configuration.
– Parcly Taxel
Jul 19 at 6:10
4
4
A wild guess: Perhaps one might prove that at least $8$ dominoes are required to allow a placement to which no further domino can be added without two dominoes sharing an edge? Aha -- your new comment above seems to suggest that this is indeed what you had in mind. Then my suggestion above was the wrong clarification of the original question.
– joriki
Jul 19 at 6:14
A wild guess: Perhaps one might prove that at least $8$ dominoes are required to allow a placement to which no further domino can be added without two dominoes sharing an edge? Aha -- your new comment above seems to suggest that this is indeed what you had in mind. Then my suggestion above was the wrong clarification of the original question.
– joriki
Jul 19 at 6:14
1
1
I think the wording of the question needs to be changed, otherwise 8 isn't the answer. Seems Joriki's last comment might be the right wording.
– coffeemath
Jul 19 at 6:17
I think the wording of the question needs to be changed, otherwise 8 isn't the answer. Seems Joriki's last comment might be the right wording.
– coffeemath
Jul 19 at 6:17
1
1
@LoveInvariants on zero you have empty spaces where you can add an domino without it sharing an edge. Similarly this is the case up till 7 where no placement exists such as the one in the picture where adding another domino is impossible without it sharing an edge with the other.
– Rumi
Jul 19 at 6:23
@LoveInvariants on zero you have empty spaces where you can add an domino without it sharing an edge. Similarly this is the case up till 7 where no placement exists such as the one in the picture where adding another domino is impossible without it sharing an edge with the other.
– Rumi
Jul 19 at 6:23
 |Â
show 7 more comments
3 Answers
3
active
oldest
votes
up vote
5
down vote
What seemed a simple question at first turned into a programming challenge. Yes, 8 dominos are required to mandate edge-to-edge contacts with further dominoes, but my eventual approach was somewhat strange…
Instead of thinking about the squares of the grid, think of the edges between adjacent squares, of which there are $2×8×7=112$. Now look at a domino:
On the left, the domino itself is in a deep blue. A new domino makes edge-to-edge contact or overlaps the original domino iff the new domino overlaps a light blue square iff the edge between the new domino's two squares coincides with any of the short purple line segments. This set of at most 23 edges I will refer to as the original domino's zone (if close to the board's edge, some segments may lie off the board or fall on the board's boundary; we do not consider such edges).
The problem of placing dominos to mandate edge-to-edge contacts – a dominating covering – now becomes a problem of covering all 112 edges by domino zones. If an edge does not lie in any zone, it can serve as the middle edge of a new domino, with no edge contact.
Now consider the configurations of zones that can cover the two edges incident to a corner square. There are five distinct viable configurations up to reflection, which I will call type 1 to type 5 from left to right:
The two crossed-out configurations are not viable, because they can be replaced by the configurations immediately below them without uncovering any covered edges. Any dominating covering needs four of these configurations, one for each corner.
We can quite easily show that we can only use at most one instance of the type 4 and type 5 configurations combined. None of the configurations covers the following edges:
Furthermore, at least two zones are required to cover these edges, which means that the corner configurations can use at most five zones.
The last step is to prove that none of the combinations of corner configurations with five and four zones extend to a complete dominating covering on 7 dominos. For this I turned to the computer, brute-forcing each combination of corner configurations and remaining domino zones to show that every one of them could not cover all 112 edges, in a manner reminiscent of Zygalski sheets. The (Python + NumPy) code can be found here. Briefly, I eliminated type 5 from consideration first, showing that no dominating covering could use it. Then I did the same with types 4, 1, 2 and finally 3, proving the non-existence of 7-domino dominating coverings of the 8×8 board.
However, there do exist near-dominating coverings that cover 111 of 112 edges (leaving exactly one place for a new domino without making edge contact). Here is one:
The SVG source of the images in this answer can be found here.
answered Jul 19 at 6:27
Parcly Taxel
33.6k136588
Can this approach be applied to any n * n grid then ? For instance 4 x 4 would have the optimum solution of 2 ?
– Rumi
Jul 19 at 6:39
2
Parcly-- In the placement of OP diagram, there are 11 squares not in zones. So in that sense goal not to place dominoes so zones cover all 64 squares. Some covered squares (3 I think) in OP diagram are shared by 2 zones... and with 7 dominoes whose zones cover the max of 56 squares, there may be say 8 squares not in zones; this doesn't seem immediately impossible given OP diagram where 11 are not in zones. As you can see I may be confused about your argument.
– coffeemath
Jul 19 at 8:14
@ParclyTaxel I agree with the above comment now. For a 9 by 9 grid I have a solution of 9. 8 * 9 is 72 which is less then 9 * 9 = 81, yet this grid still works.
– Rumi
Jul 19 at 8:27
4
Parcly Taxel, I thought of this argument in the morning, too. But for it to work you need to show that those 7x8 squares cannot be distributed in such a way that the only remaining holes are isolated. After all, to place a domino according to the rules you need two adjacent squares outside of the forbidden zone..
– Jyrki Lahtonen
Jul 19 at 11:53
@JyrkiLahtonen proof done, see updated answer.
– Parcly Taxel
Jul 19 at 17:20
 |Â
show 7 more comments
up vote
1
down vote
Partial answer only...
Naming: We will call the initial set of dominoes the "blockers". They collectively make it impossible to place an "invader" domino without the invader sharing an edge with some blocker. The OP asks for a proof that $N=8$ blockers are necessary on an $8 times 8$ board. My answer proves a lesser result:
If the blockers are not allowed to touch the board edges, then $N=8$ are necessary and sufficient.
Sufficiency:
8 . . . . . . . .
7 . x . x . x x .
6 . x . x . . . .
5 . . . . . x x .
4 . x x . . . . .
3 . . . . x . x .
2 . x x . x . x .
1 . . . . . . . .
a b c d e f g h
Necessity:
Since the blockers are not allowed to touch any board edge (in my version), some blocker must occupy b2 in order to prevent an invader at a12. Similarly blockers must occupy b7, g2 & g7. These 4 blockers, no matter how each is oriented, will leave de1, de8, a45, h45 as 4 possible locations for the invader. We will need an extra blocker to eliminate each of these 4 possible invader locations. Thus 8 blockers are necessary.
Further thoughts: As mentioned, this proof is incomplete. I tried to prove that allowing blockers to touch the board edges (as in the OP sample solution) cannot make the blocking task EASIER (i.e. $N < 8$), but without success... Simple transformations don't seem to work. E.g. in the OP solution, the blockers at a34 and cd1 collectively prevent any intruder at a1, and we cannot move either blocker off the board edge without a whole series of other moves.
answered Jul 19 at 15:44
antkam
1,209111
add a comment |Â
up vote
0
down vote
Maybe this helps.
Least no. of dominoes which can be placed on $8times 6$ rectangle is $4$. You can prove it by dividing $8times 6$ rectangle into $4, 4times 3$ rectangles.
The remaining $8times 2$ grid can have 4 dominoes.
answered Jul 19 at 6:32
Love Invariants
81215
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
What seemed a simple question at first turned into a programming challenge. Yes, 8 dominos are required to mandate edge-to-edge contacts with further dominoes, but my eventual approach was somewhat strange…
Instead of thinking about the squares of the grid, think of the edges between adjacent squares, of which there are $2×8×7=112$. Now look at a domino:
On the left, the domino itself is in a deep blue. A new domino makes edge-to-edge contact or overlaps the original domino iff the new domino overlaps a light blue square iff the edge between the new domino's two squares coincides with any of the short purple line segments. This set of at most 23 edges I will refer to as the original domino's zone (if close to the board's edge, some segments may lie off the board or fall on the board's boundary; we do not consider such edges).
The problem of placing dominos to mandate edge-to-edge contacts – a dominating covering – now becomes a problem of covering all 112 edges by domino zones. If an edge does not lie in any zone, it can serve as the middle edge of a new domino, with no edge contact.
Now consider the configurations of zones that can cover the two edges incident to a corner square. There are five distinct viable configurations up to reflection, which I will call type 1 to type 5 from left to right:
The two crossed-out configurations are not viable, because they can be replaced by the configurations immediately below them without uncovering any covered edges. Any dominating covering needs four of these configurations, one for each corner.
We can quite easily show that we can only use at most one instance of the type 4 and type 5 configurations combined. None of the configurations covers the following edges:
Furthermore, at least two zones are required to cover these edges, which means that the corner configurations can use at most five zones.
The last step is to prove that none of the combinations of corner configurations with five and four zones extend to a complete dominating covering on 7 dominos. For this I turned to the computer, brute-forcing each combination of corner configurations and remaining domino zones to show that every one of them could not cover all 112 edges, in a manner reminiscent of Zygalski sheets. The (Python + NumPy) code can be found here. Briefly, I eliminated type 5 from consideration first, showing that no dominating covering could use it. Then I did the same with types 4, 1, 2 and finally 3, proving the non-existence of 7-domino dominating coverings of the 8×8 board.
However, there do exist near-dominating coverings that cover 111 of 112 edges (leaving exactly one place for a new domino without making edge contact). Here is one:
The SVG source of the images in this answer can be found here.
answered Jul 19 at 6:27
Parcly Taxel
33.6k136588
Can this approach be applied to any n * n grid then ? For instance 4 x 4 would have the optimum solution of 2 ?
– Rumi
Jul 19 at 6:39
2
Parcly-- In the placement of OP diagram, there are 11 squares not in zones. So in that sense goal not to place dominoes so zones cover all 64 squares. Some covered squares (3 I think) in OP diagram are shared by 2 zones... and with 7 dominoes whose zones cover the max of 56 squares, there may be say 8 squares not in zones; this doesn't seem immediately impossible given OP diagram where 11 are not in zones. As you can see I may be confused about your argument.
– coffeemath
Jul 19 at 8:14
@ParclyTaxel I agree with the above comment now. For a 9 by 9 grid I have a solution of 9. 8 * 9 is 72 which is less then 9 * 9 = 81, yet this grid still works.
– Rumi
Jul 19 at 8:27
4
Parcly Taxel, I thought of this argument in the morning, too. But for it to work you need to show that those 7x8 squares cannot be distributed in such a way that the only remaining holes are isolated. After all, to place a domino according to the rules you need two adjacent squares outside of the forbidden zone..
– Jyrki Lahtonen
Jul 19 at 11:53
@JyrkiLahtonen proof done, see updated answer.
– Parcly Taxel
Jul 19 at 17:20
 |Â
show 7 more comments
up vote
5
down vote
What seemed a simple question at first turned into a programming challenge. Yes, 8 dominos are required to mandate edge-to-edge contacts with further dominoes, but my eventual approach was somewhat strange…
Instead of thinking about the squares of the grid, think of the edges between adjacent squares, of which there are $2×8×7=112$. Now look at a domino:
On the left, the domino itself is in a deep blue. A new domino makes edge-to-edge contact or overlaps the original domino iff the new domino overlaps a light blue square iff the edge between the new domino's two squares coincides with any of the short purple line segments. This set of at most 23 edges I will refer to as the original domino's zone (if close to the board's edge, some segments may lie off the board or fall on the board's boundary; we do not consider such edges).
The problem of placing dominos to mandate edge-to-edge contacts – a dominating covering – now becomes a problem of covering all 112 edges by domino zones. If an edge does not lie in any zone, it can serve as the middle edge of a new domino, with no edge contact.
Now consider the configurations of zones that can cover the two edges incident to a corner square. There are five distinct viable configurations up to reflection, which I will call type 1 to type 5 from left to right:
The two crossed-out configurations are not viable, because they can be replaced by the configurations immediately below them without uncovering any covered edges. Any dominating covering needs four of these configurations, one for each corner.
We can quite easily show that we can only use at most one instance of the type 4 and type 5 configurations combined. None of the configurations covers the following edges:
Furthermore, at least two zones are required to cover these edges, which means that the corner configurations can use at most five zones.
The last step is to prove that none of the combinations of corner configurations with five and four zones extend to a complete dominating covering on 7 dominos. For this I turned to the computer, brute-forcing each combination of corner configurations and remaining domino zones to show that every one of them could not cover all 112 edges, in a manner reminiscent of Zygalski sheets. The (Python + NumPy) code can be found here. Briefly, I eliminated type 5 from consideration first, showing that no dominating covering could use it. Then I did the same with types 4, 1, 2 and finally 3, proving the non-existence of 7-domino dominating coverings of the 8×8 board.
However, there do exist near-dominating coverings that cover 111 of 112 edges (leaving exactly one place for a new domino without making edge contact). Here is one:
The SVG source of the images in this answer can be found here.
answered Jul 19 at 6:27
Parcly Taxel
33.6k136588
Can this approach be applied to any n * n grid then ? For instance 4 x 4 would have the optimum solution of 2 ?
– Rumi
Jul 19 at 6:39
2
Parcly-- In the placement of OP diagram, there are 11 squares not in zones. So in that sense goal not to place dominoes so zones cover all 64 squares. Some covered squares (3 I think) in OP diagram are shared by 2 zones... and with 7 dominoes whose zones cover the max of 56 squares, there may be say 8 squares not in zones; this doesn't seem immediately impossible given OP diagram where 11 are not in zones. As you can see I may be confused about your argument.
– coffeemath
Jul 19 at 8:14
@ParclyTaxel I agree with the above comment now. For a 9 by 9 grid I have a solution of 9. 8 * 9 is 72 which is less then 9 * 9 = 81, yet this grid still works.
– Rumi
Jul 19 at 8:27
4
Parcly Taxel, I thought of this argument in the morning, too. But for it to work you need to show that those 7x8 squares cannot be distributed in such a way that the only remaining holes are isolated. After all, to place a domino according to the rules you need two adjacent squares outside of the forbidden zone..
– Jyrki Lahtonen
Jul 19 at 11:53
@JyrkiLahtonen proof done, see updated answer.
– Parcly Taxel
Jul 19 at 17:20
 |Â
show 7 more comments
up vote
5
down vote
up vote
5
down vote
What seemed a simple question at first turned into a programming challenge. Yes, 8 dominos are required to mandate edge-to-edge contacts with further dominoes, but my eventual approach was somewhat strange…
Instead of thinking about the squares of the grid, think of the edges between adjacent squares, of which there are $2×8×7=112$. Now look at a domino:
On the left, the domino itself is in a deep blue. A new domino makes edge-to-edge contact or overlaps the original domino iff the new domino overlaps a light blue square iff the edge between the new domino's two squares coincides with any of the short purple line segments. This set of at most 23 edges I will refer to as the original domino's zone (if close to the board's edge, some segments may lie off the board or fall on the board's boundary; we do not consider such edges).
The problem of placing dominos to mandate edge-to-edge contacts – a dominating covering – now becomes a problem of covering all 112 edges by domino zones. If an edge does not lie in any zone, it can serve as the middle edge of a new domino, with no edge contact.
Now consider the configurations of zones that can cover the two edges incident to a corner square. There are five distinct viable configurations up to reflection, which I will call type 1 to type 5 from left to right:
The two crossed-out configurations are not viable, because they can be replaced by the configurations immediately below them without uncovering any covered edges. Any dominating covering needs four of these configurations, one for each corner.
We can quite easily show that we can only use at most one instance of the type 4 and type 5 configurations combined. None of the configurations covers the following edges:
Furthermore, at least two zones are required to cover these edges, which means that the corner configurations can use at most five zones.
The last step is to prove that none of the combinations of corner configurations with five and four zones extend to a complete dominating covering on 7 dominos. For this I turned to the computer, brute-forcing each combination of corner configurations and remaining domino zones to show that every one of them could not cover all 112 edges, in a manner reminiscent of Zygalski sheets. The (Python + NumPy) code can be found here. Briefly, I eliminated type 5 from consideration first, showing that no dominating covering could use it. Then I did the same with types 4, 1, 2 and finally 3, proving the non-existence of 7-domino dominating coverings of the 8×8 board.
However, there do exist near-dominating coverings that cover 111 of 112 edges (leaving exactly one place for a new domino without making edge contact). Here is one:
The SVG source of the images in this answer can be found here.
answered Jul 19 at 6:27
Parcly Taxel
33.6k136588
What seemed a simple question at first turned into a programming challenge. Yes, 8 dominos are required to mandate edge-to-edge contacts with further dominoes, but my eventual approach was somewhat strange…
Instead of thinking about the squares of the grid, think of the edges between adjacent squares, of which there are $2×8×7=112$. Now look at a domino:
On the left, the domino itself is in a deep blue. A new domino makes edge-to-edge contact or overlaps the original domino iff the new domino overlaps a light blue square iff the edge between the new domino's two squares coincides with any of the short purple line segments. This set of at most 23 edges I will refer to as the original domino's zone (if close to the board's edge, some segments may lie off the board or fall on the board's boundary; we do not consider such edges).
The problem of placing dominos to mandate edge-to-edge contacts – a dominating covering – now becomes a problem of covering all 112 edges by domino zones. If an edge does not lie in any zone, it can serve as the middle edge of a new domino, with no edge contact.
Now consider the configurations of zones that can cover the two edges incident to a corner square. There are five distinct viable configurations up to reflection, which I will call type 1 to type 5 from left to right:
The two crossed-out configurations are not viable, because they can be replaced by the configurations immediately below them without uncovering any covered edges. Any dominating covering needs four of these configurations, one for each corner.
We can quite easily show that we can only use at most one instance of the type 4 and type 5 configurations combined. None of the configurations covers the following edges:
Furthermore, at least two zones are required to cover these edges, which means that the corner configurations can use at most five zones.
The last step is to prove that none of the combinations of corner configurations with five and four zones extend to a complete dominating covering on 7 dominos. For this I turned to the computer, brute-forcing each combination of corner configurations and remaining domino zones to show that every one of them could not cover all 112 edges, in a manner reminiscent of Zygalski sheets. The (Python + NumPy) code can be found here. Briefly, I eliminated type 5 from consideration first, showing that no dominating covering could use it. Then I did the same with types 4, 1, 2 and finally 3, proving the non-existence of 7-domino dominating coverings of the 8×8 board.
However, there do exist near-dominating coverings that cover 111 of 112 edges (leaving exactly one place for a new domino without making edge contact). Here is one:
The SVG source of the images in this answer can be found here.
answered Jul 19 at 6:27
Parcly Taxel
33.6k136588
edited Jul 19 at 17:19
answered Jul 19 at 6:27
Parcly Taxel
33.6k136588
answered Jul 19 at 6:27
Parcly Taxel
33.6k136588
answered Jul 19 at 6:27
Parcly Taxel
33.6k136588
33.6k136588
Can this approach be applied to any n * n grid then ? For instance 4 x 4 would have the optimum solution of 2 ?
– Rumi
Jul 19 at 6:39
2
Parcly-- In the placement of OP diagram, there are 11 squares not in zones. So in that sense goal not to place dominoes so zones cover all 64 squares. Some covered squares (3 I think) in OP diagram are shared by 2 zones... and with 7 dominoes whose zones cover the max of 56 squares, there may be say 8 squares not in zones; this doesn't seem immediately impossible given OP diagram where 11 are not in zones. As you can see I may be confused about your argument.
– coffeemath
Jul 19 at 8:14
@ParclyTaxel I agree with the above comment now. For a 9 by 9 grid I have a solution of 9. 8 * 9 is 72 which is less then 9 * 9 = 81, yet this grid still works.
– Rumi
Jul 19 at 8:27
4
Parcly Taxel, I thought of this argument in the morning, too. But for it to work you need to show that those 7x8 squares cannot be distributed in such a way that the only remaining holes are isolated. After all, to place a domino according to the rules you need two adjacent squares outside of the forbidden zone..
– Jyrki Lahtonen
Jul 19 at 11:53
@JyrkiLahtonen proof done, see updated answer.
– Parcly Taxel
Jul 19 at 17:20
 |Â
show 7 more comments
Can this approach be applied to any n * n grid then ? For instance 4 x 4 would have the optimum solution of 2 ?
– Rumi
Jul 19 at 6:39
2
Parcly-- In the placement of OP diagram, there are 11 squares not in zones. So in that sense goal not to place dominoes so zones cover all 64 squares. Some covered squares (3 I think) in OP diagram are shared by 2 zones... and with 7 dominoes whose zones cover the max of 56 squares, there may be say 8 squares not in zones; this doesn't seem immediately impossible given OP diagram where 11 are not in zones. As you can see I may be confused about your argument.
– coffeemath
Jul 19 at 8:14
@ParclyTaxel I agree with the above comment now. For a 9 by 9 grid I have a solution of 9. 8 * 9 is 72 which is less then 9 * 9 = 81, yet this grid still works.
– Rumi
Jul 19 at 8:27
4
Parcly Taxel, I thought of this argument in the morning, too. But for it to work you need to show that those 7x8 squares cannot be distributed in such a way that the only remaining holes are isolated. After all, to place a domino according to the rules you need two adjacent squares outside of the forbidden zone..
– Jyrki Lahtonen
Jul 19 at 11:53
@JyrkiLahtonen proof done, see updated answer.
– Parcly Taxel
Jul 19 at 17:20
Can this approach be applied to any n * n grid then ? For instance 4 x 4 would have the optimum solution of 2 ?
– Rumi
Jul 19 at 6:39
Can this approach be applied to any n * n grid then ? For instance 4 x 4 would have the optimum solution of 2 ?
– Rumi
Jul 19 at 6:39
2
2
Parcly-- In the placement of OP diagram, there are 11 squares not in zones. So in that sense goal not to place dominoes so zones cover all 64 squares. Some covered squares (3 I think) in OP diagram are shared by 2 zones... and with 7 dominoes whose zones cover the max of 56 squares, there may be say 8 squares not in zones; this doesn't seem immediately impossible given OP diagram where 11 are not in zones. As you can see I may be confused about your argument.
– coffeemath
Jul 19 at 8:14
Parcly-- In the placement of OP diagram, there are 11 squares not in zones. So in that sense goal not to place dominoes so zones cover all 64 squares. Some covered squares (3 I think) in OP diagram are shared by 2 zones... and with 7 dominoes whose zones cover the max of 56 squares, there may be say 8 squares not in zones; this doesn't seem immediately impossible given OP diagram where 11 are not in zones. As you can see I may be confused about your argument.
– coffeemath
Jul 19 at 8:14
@ParclyTaxel I agree with the above comment now. For a 9 by 9 grid I have a solution of 9. 8 * 9 is 72 which is less then 9 * 9 = 81, yet this grid still works.
– Rumi
Jul 19 at 8:27
@ParclyTaxel I agree with the above comment now. For a 9 by 9 grid I have a solution of 9. 8 * 9 is 72 which is less then 9 * 9 = 81, yet this grid still works.
– Rumi
Jul 19 at 8:27
4
4
Parcly Taxel, I thought of this argument in the morning, too. But for it to work you need to show that those 7x8 squares cannot be distributed in such a way that the only remaining holes are isolated. After all, to place a domino according to the rules you need two adjacent squares outside of the forbidden zone..
– Jyrki Lahtonen
Jul 19 at 11:53
Parcly Taxel, I thought of this argument in the morning, too. But for it to work you need to show that those 7x8 squares cannot be distributed in such a way that the only remaining holes are isolated. After all, to place a domino according to the rules you need two adjacent squares outside of the forbidden zone..
– Jyrki Lahtonen
Jul 19 at 11:53
@JyrkiLahtonen proof done, see updated answer.
– Parcly Taxel
Jul 19 at 17:20
@JyrkiLahtonen proof done, see updated answer.
– Parcly Taxel
Jul 19 at 17:20
 |Â
show 7 more comments
up vote
1
down vote
Partial answer only...
Naming: We will call the initial set of dominoes the "blockers". They collectively make it impossible to place an "invader" domino without the invader sharing an edge with some blocker. The OP asks for a proof that $N=8$ blockers are necessary on an $8 times 8$ board. My answer proves a lesser result:
If the blockers are not allowed to touch the board edges, then $N=8$ are necessary and sufficient.
Sufficiency:
8 . . . . . . . .
7 . x . x . x x .
6 . x . x . . . .
5 . . . . . x x .
4 . x x . . . . .
3 . . . . x . x .
2 . x x . x . x .
1 . . . . . . . .
a b c d e f g h
Necessity:
Since the blockers are not allowed to touch any board edge (in my version), some blocker must occupy b2 in order to prevent an invader at a12. Similarly blockers must occupy b7, g2 & g7. These 4 blockers, no matter how each is oriented, will leave de1, de8, a45, h45 as 4 possible locations for the invader. We will need an extra blocker to eliminate each of these 4 possible invader locations. Thus 8 blockers are necessary.
Further thoughts: As mentioned, this proof is incomplete. I tried to prove that allowing blockers to touch the board edges (as in the OP sample solution) cannot make the blocking task EASIER (i.e. $N < 8$), but without success... Simple transformations don't seem to work. E.g. in the OP solution, the blockers at a34 and cd1 collectively prevent any intruder at a1, and we cannot move either blocker off the board edge without a whole series of other moves.
answered Jul 19 at 15:44
antkam
1,209111
add a comment |Â
up vote
1
down vote
Partial answer only...
Naming: We will call the initial set of dominoes the "blockers". They collectively make it impossible to place an "invader" domino without the invader sharing an edge with some blocker. The OP asks for a proof that $N=8$ blockers are necessary on an $8 times 8$ board. My answer proves a lesser result:
If the blockers are not allowed to touch the board edges, then $N=8$ are necessary and sufficient.
Sufficiency:
8 . . . . . . . .
7 . x . x . x x .
6 . x . x . . . .
5 . . . . . x x .
4 . x x . . . . .
3 . . . . x . x .
2 . x x . x . x .
1 . . . . . . . .
a b c d e f g h
Necessity:
Since the blockers are not allowed to touch any board edge (in my version), some blocker must occupy b2 in order to prevent an invader at a12. Similarly blockers must occupy b7, g2 & g7. These 4 blockers, no matter how each is oriented, will leave de1, de8, a45, h45 as 4 possible locations for the invader. We will need an extra blocker to eliminate each of these 4 possible invader locations. Thus 8 blockers are necessary.
Further thoughts: As mentioned, this proof is incomplete. I tried to prove that allowing blockers to touch the board edges (as in the OP sample solution) cannot make the blocking task EASIER (i.e. $N < 8$), but without success... Simple transformations don't seem to work. E.g. in the OP solution, the blockers at a34 and cd1 collectively prevent any intruder at a1, and we cannot move either blocker off the board edge without a whole series of other moves.
answered Jul 19 at 15:44
antkam
1,209111
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Partial answer only...
Naming: We will call the initial set of dominoes the "blockers". They collectively make it impossible to place an "invader" domino without the invader sharing an edge with some blocker. The OP asks for a proof that $N=8$ blockers are necessary on an $8 times 8$ board. My answer proves a lesser result:
If the blockers are not allowed to touch the board edges, then $N=8$ are necessary and sufficient.
Sufficiency:
8 . . . . . . . .
7 . x . x . x x .
6 . x . x . . . .
5 . . . . . x x .
4 . x x . . . . .
3 . . . . x . x .
2 . x x . x . x .
1 . . . . . . . .
a b c d e f g h
Necessity:
Since the blockers are not allowed to touch any board edge (in my version), some blocker must occupy b2 in order to prevent an invader at a12. Similarly blockers must occupy b7, g2 & g7. These 4 blockers, no matter how each is oriented, will leave de1, de8, a45, h45 as 4 possible locations for the invader. We will need an extra blocker to eliminate each of these 4 possible invader locations. Thus 8 blockers are necessary.
Further thoughts: As mentioned, this proof is incomplete. I tried to prove that allowing blockers to touch the board edges (as in the OP sample solution) cannot make the blocking task EASIER (i.e. $N < 8$), but without success... Simple transformations don't seem to work. E.g. in the OP solution, the blockers at a34 and cd1 collectively prevent any intruder at a1, and we cannot move either blocker off the board edge without a whole series of other moves.
answered Jul 19 at 15:44
antkam
1,209111
Partial answer only...
Naming: We will call the initial set of dominoes the "blockers". They collectively make it impossible to place an "invader" domino without the invader sharing an edge with some blocker. The OP asks for a proof that $N=8$ blockers are necessary on an $8 times 8$ board. My answer proves a lesser result:
If the blockers are not allowed to touch the board edges, then $N=8$ are necessary and sufficient.
Sufficiency:
8 . . . . . . . .
7 . x . x . x x .
6 . x . x . . . .
5 . . . . . x x .
4 . x x . . . . .
3 . . . . x . x .
2 . x x . x . x .
1 . . . . . . . .
a b c d e f g h
Necessity:
Since the blockers are not allowed to touch any board edge (in my version), some blocker must occupy b2 in order to prevent an invader at a12. Similarly blockers must occupy b7, g2 & g7. These 4 blockers, no matter how each is oriented, will leave de1, de8, a45, h45 as 4 possible locations for the invader. We will need an extra blocker to eliminate each of these 4 possible invader locations. Thus 8 blockers are necessary.
Further thoughts: As mentioned, this proof is incomplete. I tried to prove that allowing blockers to touch the board edges (as in the OP sample solution) cannot make the blocking task EASIER (i.e. $N < 8$), but without success... Simple transformations don't seem to work. E.g. in the OP solution, the blockers at a34 and cd1 collectively prevent any intruder at a1, and we cannot move either blocker off the board edge without a whole series of other moves.
answered Jul 19 at 15:44
antkam
1,209111
answered Jul 19 at 15:44
antkam
1,209111
answered Jul 19 at 15:44
antkam
1,209111
answered Jul 19 at 15:44
antkam
1,209111
1,209111
add a comment |Â
add a comment |Â
up vote
0
down vote
Maybe this helps.
Least no. of dominoes which can be placed on $8times 6$ rectangle is $4$. You can prove it by dividing $8times 6$ rectangle into $4, 4times 3$ rectangles.
The remaining $8times 2$ grid can have 4 dominoes.
answered Jul 19 at 6:32
Love Invariants
81215
add a comment |Â
up vote
0
down vote
Maybe this helps.
Least no. of dominoes which can be placed on $8times 6$ rectangle is $4$. You can prove it by dividing $8times 6$ rectangle into $4, 4times 3$ rectangles.
The remaining $8times 2$ grid can have 4 dominoes.
answered Jul 19 at 6:32
Love Invariants
81215
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Maybe this helps.
Least no. of dominoes which can be placed on $8times 6$ rectangle is $4$. You can prove it by dividing $8times 6$ rectangle into $4, 4times 3$ rectangles.
The remaining $8times 2$ grid can have 4 dominoes.
answered Jul 19 at 6:32
Love Invariants
81215
Maybe this helps.
Least no. of dominoes which can be placed on $8times 6$ rectangle is $4$. You can prove it by dividing $8times 6$ rectangle into $4, 4times 3$ rectangles.
The remaining $8times 2$ grid can have 4 dominoes.
answered Jul 19 at 6:32
Love Invariants
81215
answered Jul 19 at 6:32
Love Invariants
81215
answered Jul 19 at 6:32
Love Invariants
81215
answered Jul 19 at 6:32
Love Invariants
81215
81215
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2856311%2fdomino-tiling-8-x-8-grid-proof%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
I suggest reformulating the question as "How can I prove that on an $8$ x $8$ grid, 8 is the maximum number of dominoes I can place such that no two dominoes share an edge?". In the current formulation, the requirement that the first $8$ dominoes don't share an edge is missing; the claim would be trivially wrong if taken literally.
– joriki
Jul 19 at 6:09
2
@JyrkiLahtonen You could easily place 16 dominoes in an admissible configuration.
– Parcly Taxel
Jul 19 at 6:10
4
A wild guess: Perhaps one might prove that at least $8$ dominoes are required to allow a placement to which no further domino can be added without two dominoes sharing an edge? Aha -- your new comment above seems to suggest that this is indeed what you had in mind. Then my suggestion above was the wrong clarification of the original question.
– joriki
Jul 19 at 6:14
1
I think the wording of the question needs to be changed, otherwise 8 isn't the answer. Seems Joriki's last comment might be the right wording.
– coffeemath
Jul 19 at 6:17
1
@LoveInvariants on zero you have empty spaces where you can add an domino without it sharing an edge. Similarly this is the case up till 7 where no placement exists such as the one in the picture where adding another domino is impossible without it sharing an edge with the other.
– Rumi
Jul 19 at 6:23