Donate to Remove ads

Got a credit card? use our Credit Card & Finance Calculators

Thanks to Anonymous,johnhemming,Anonymous,Rhyd6,dredd0, for Donating to support the site

Dominoes

cinelli
Lemon Slice
Posts: 304
Joined: November 9th, 2016, 11:33 am
Has thanked: 93 times
Been thanked: 53 times

Dominoes

#320430

Postby cinelli » June 22nd, 2020, 12:55 pm

.-- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx|
-- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx| | | |
-- -- -- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx|
-- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx|
-- -- -- -- -- -- -- --

If two squares of opposite colours are removed from anywhere on an 8x8 chessboard, can the remaining portion of the board be completely covered with 1x2 dominoes? If so can you show how it can be done? If not prove it.

Cinelli

Gengulphus
Lemon Quarter
Posts: 3226
Joined: November 4th, 2016, 1:17 am
Been thanked: 1758 times

Re: Dominoes

#320462

Postby Gengulphus » June 22nd, 2020, 3:37 pm

cinelli wrote:
.-- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx|
-- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx| | | |
-- -- -- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx|
-- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx|
-- -- -- -- -- -- -- --

If two squares of opposite colours are removed from anywhere on an 8x8 chessboard, can the remaining portion of the board be completely covered with 1x2 dominoes? If so can you show how it can be done? If not prove it.

Spoiler...

Yes, it can always be completely covered with 1x2 dominoes. The two removed squares are in different rows, different columns or both. So I can split into four cases:

  1. the row containing the black removed square is above the row containing the white removed square;
  2. the row containing the black removed square is below the row containing the white removed square;
  3. the column containing the black removed square is to the left of the column containing the white removed square;
  4. the column containing the black removed square is to the right of the column containing the white removed square.
In case 1, consider the path from the top left corner to the bottom left corner that goes from left to right along the top row, then right to left along the 2nd row, then left to right along the 3rd row, etc, ending up going right to left along the bottom row. If I head along it laying down dominoes as I go, I will reach the black removed square before I reach the white removed square, so each domino covers a black square and then a white square until I reach the black removed square, then each domino covers a white square and then a black square until I reach the white removed square, then each domino covers a black square and then a white square until I end up in the bottom left corner, and I have successfully covered the board minus the removed squares with dominos.

In case 2, do likewise with the symmetrically placed path from the bottom right corner to the top right corner that starts by going right to left along the bottom row; in case 3, do likewise with the symmetrically placed path from the top left corner to the top right corner that starts by going top to bottom down the leftmost column; in case 4, do likewise with the symmetrically placed path from the bottom right corner to the bottom left corner that starts by going bottom to top up the rightmost column. (Note that if the two removed squares are neither in the same row nor the same column, both one of cases 1 and 2 and one of cases 3 and 4 apply, giving two different solutions - but that's no problem!)

Gengulphus

cinelli
Lemon Slice
Posts: 304
Joined: November 9th, 2016, 11:33 am
Has thanked: 93 times
Been thanked: 53 times

Re: Dominoes

#321336

Postby cinelli » June 25th, 2020, 11:41 am

Well solved Gengulphus. On reflection I think I should have worded the question differently: “Are there any choices of the two squares which make it impossible to cover the remaining squares with dominoes?” But you have shown that it is possible in all cases.

My solution is not very different from yours. Instead of going from top left to bottom left. I made a closed loop as follows:

.-- -- -- -- -- -- -- --
| |
-- -- -- -- -- --
| | | | | |

| | | | | | | | |

| | | | | | | | |

| | | | | | | | |

| | | | | | | | |

| | | | | | | | |

| | | | |
-- -- -- -- -- -- -- --

This choice is by no means unique but it has a pleasing symmetry. The squares lie with alternating colours along the closed path. The removal of two squares of opposite colours from any two spots along the path will cut the path into two open-ended segments (or one if the two removed squares are adjacent on the path). Since each segment must consist of an even number of squares, each segment, and therefore the entire board, can be completely covered by dominoes.

Cinelli

Gengulphus
Lemon Quarter
Posts: 3226
Joined: November 4th, 2016, 1:17 am
Been thanked: 1758 times

Re: Dominoes

#321622

Postby Gengulphus » June 26th, 2020, 4:59 am

cinelli wrote:Well solved Gengulphus. On reflection I think I should have worded the question differently: “Are there any choices of the two squares which make it impossible to cover the remaining squares with dominoes?” But you have shown that it is possible in all cases.

My solution is not very different from yours. Instead of going from top left to bottom left. I made a closed loop as follows:

.-- -- -- -- -- -- -- --
| |
-- -- -- -- -- --
| | | | | |

| | | | | | | | |

| | | | | | | | |

| | | | | | | | |

| | | | | | | | |

| | | | | | | | |

| | | | |
-- -- -- -- -- -- -- --

This choice is by no means unique but it has a pleasing symmetry. The squares lie with alternating colours along the closed path. The removal of two squares of opposite colours from any two spots along the path will cut the path into two open-ended segments (or one if the two removed squares are adjacent on the path). Since each segment must consist of an even number of squares, each segment, and therefore the entire board, can be completely covered by dominoes.

Yes, that's a slightly better solution than mine, as it doesn't involve splitting into cases at all, whereas mine involves splitting into four cases - albeit four cases that are equivalent under the square's symmetries.

By the way, here's a closed loop that has even better symmetry:

+-----+-----+-----+-----+
| | | | |
| + | + | + | + |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | + | + | + | |
| | | | | |
| +-----+-----+-----+ |
| | | | | |
| | + | + | + | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| + | + | + | + |
| | | | |
+-----+-----+-----+-----+

As a follow-up puzzle that I don't have the answer to (or at least not yet!), suppose we remove two black squares and two white squares, without isolating any of the corner squares by removing the two adjacent squares and not removing the corner square itself. Can one always cover the remaining squares with dominoes, or are there other cases in which they cannot be covered?

Gengulphus

jfgw
Lemon Quarter
Posts: 1231
Joined: November 4th, 2016, 3:36 pm
Has thanked: 202 times
Been thanked: 331 times

Re: Dominoes

#321689

Postby jfgw » June 26th, 2020, 9:57 am

Gengulphus wrote:As a follow-up puzzle that I don't have the answer to (or at least not yet!), suppose we remove two black squares and two white squares, without isolating any of the corner squares by removing the two adjacent squares and not removing the corner square itself. Can one always cover the remaining squares with dominoes, or are there other cases in which they cannot be covered?


You need to also eliminate the case where three squares in a corner are isolated by removing (say) A3, B2 and C1 otherwise the puzzle is too easy :)


Julian F. G. W.

UncleEbenezer
Lemon Quarter
Posts: 4842
Joined: November 4th, 2016, 8:17 pm
Has thanked: 589 times
Been thanked: 943 times

Re: Dominoes

#321712

Postby UncleEbenezer » June 26th, 2020, 10:30 am

jfgw wrote:You need to also eliminate the case where three squares in a corner are isolated by removing (say) A3, B2 and C1 otherwise the puzzle is too easy :)
Julian F. G. W.

Two of each colour already excludes that. But I agree the principle of making special cases detracts from the problem.

Perhaps Gengulphus' problem should be generalised to removing N white and N black squares, with the condition that remaining space be connected? We've dealt with N<=1, and at the other extreme if N>=30 the connected space to be dominoed is so constrained as to be trivial.

With intermediate N we can easily construct counterexamples. Thus with N=27 we cannot domino this remaining space:
.
o +
o + o + o +
o +


So, what values of N work, and why?

Supplementary: the condition of the space to be dominoed being connected is just the most obvious generalisation of Gengulphus' corners. But our counterexample shows it's not a sufficient condition. Can we express any reasonably elegant alternative condition?

UncleEbenezer
Lemon Quarter
Posts: 4842
Joined: November 4th, 2016, 8:17 pm
Has thanked: 589 times
Been thanked: 943 times

Re: Dominoes

#321719

Postby UncleEbenezer » June 26th, 2020, 10:49 am

Should've added: since all the example needs is a matching pair of corners, it generalises obviously to all 4 <= N <= 28

UncleEbenezer
Lemon Quarter
Posts: 4842
Joined: November 4th, 2016, 8:17 pm
Has thanked: 589 times
Been thanked: 943 times

Re: Dominoes

#321758

Postby UncleEbenezer » June 26th, 2020, 11:54 am

Bah. My mind was playing with symmetry.
We know N=0,1,30,31 work. And in addition to what I said, the simplest counterexample of all deals with N=29:
.
o
+ o + o
+


That just leaves N=2,3 unsolved. My mind wants to find symmetry with 30 and 29 respectively, but doesn't see a proof.

Gengulphus
Lemon Quarter
Posts: 3226
Joined: November 4th, 2016, 1:17 am
Been thanked: 1758 times

Re: Dominoes

#321823

Postby Gengulphus » June 26th, 2020, 1:53 pm

UncleEbenezer wrote:Bah. My mind was playing with symmetry.
We know N=0,1,30,31 work. And in addition to what I said, the simplest counterexample of all deals with N=29:
.
o
+ o + o
+


That just leaves N=2,3 unsolved. My mind wants to find symmetry with 30 and 29 respectively, but doesn't see a proof.

For N=3, just remove three squares of one colour to leave this configuration in the top left corner of the board:

+----------
| o ...
| o o o ...
| o o ...
| : : :
| : : :

and remove three squares of the other colour from elsewhere on the board so as to leave it connected - this can be done for any board of size 4x4 or more.

Gengulphus

UncleEbenezer
Lemon Quarter
Posts: 4842
Joined: November 4th, 2016, 8:17 pm
Has thanked: 589 times
Been thanked: 943 times

Re: Dominoes

#321861

Postby UncleEbenezer » June 26th, 2020, 3:43 pm

Gengulphus wrote:For N=3, just remove three squares of one colour to leave this configuration in the top left corner of the board:

Damn, that's just another variant of my example - should've been obvious. :oops:

Also feels like the kind of symmetry I was looking for. Now if we had a symmetry property with N=30, your N=2 solution would follow.

Gengulphus
Lemon Quarter
Posts: 3226
Joined: November 4th, 2016, 1:17 am
Been thanked: 1758 times

Re: Dominoes

#324529

Postby Gengulphus » July 8th, 2020, 9:35 am

Gengulphus wrote:
cinelli wrote:... Instead of going from top left to bottom left. I made a closed loop as follows:
...
This choice is by no means unique but it has a pleasing symmetry. The squares lie with alternating colours along the closed path. The removal of two squares of opposite colours from any two spots along the path will cut the path into two open-ended segments (or one if the two removed squares are adjacent on the path). Since each segment must consist of an even number of squares, each segment, and therefore the entire board, can be completely covered by dominoes.

...
As a follow-up puzzle that I don't have the answer to (or at least not yet!), suppose we remove two black squares and two white squares, without isolating any of the corner squares by removing the two adjacent squares and not removing the corner square itself. Can one always cover the remaining squares with dominoes, or are there other cases in which they cannot be covered?

One small point that has occurred to me about that follow-up puzzle. Often, one can still find a closed loop through all the squares and visits black and white removed squares alternately, in which case the four segments of that closed loop that the removed squares split it up into each contain an even (possibly zero) number of squares and so can separately be covered by dominoes. This isn't possible for the configurations I described, because the loop must visit two squares adjacent to the corner square immediately before and after visiting the corner square itself. The point that has occurred to me is that such a closed loop also isn't possible if the four removed squares are all on the edge of the board and appear in a black/black/white/white order (or some rotation of that order) as one goes around the edge of the board, as opposed to a black/white/black/white (or white/black/white/black) order. For example, if the removed squares are the ones I've marked B1, B2, W1 and W2 in the following diagram, no such closed loop exists:

+--+--+--+--+--+--+--+--+
|xx| |xx| |B1| |xx| |
+--+--+--+--+--+--+--+--+
|W2|xx| |xx| |xx| |xx|
+--+--+--+--+--+--+--+--+
|xx| |xx| |xx| |xx| |
+--+--+--+--+--+--+--+--+
| |xx| |xx| |xx| |xx|
+--+--+--+--+--+--+--+--+
|xx| |xx| |xx| |xx| |
+--+--+--+--+--+--+--+--+
| |xx| |xx| |xx| |B2|
+--+--+--+--+--+--+--+--+
|xx| |xx| |xx| |xx| |
+--+--+--+--+--+--+--+--+
|W1|xx| |xx| |xx| |xx|
+--+--+--+--+--+--+--+--+

The reason why no such closed loop exists is simply that if one did, it would be divided into four segments by the removed squares and those segments would have to be between each combination of Bi and Wj, for i = 1,2 and j = 1,2. Now look at the segment between B1 and W1 and the segment between B2 and W2: because their endpoints are all on the edge of the board, they have to cross each other somewhere, i.e. to have at least one square in common - but that's incompatible with them being two of the segments into which the removed squares split a closed loop.

So what that says is that there are many other configurations of the removed squares besides the ones I described for which there is no 'closed loop' solution. That doesn't mean that I've found any extra configurations of the removed squares that are unsolvable, just that one may have to look beyond 'closed loop' solutions. For example, the above board has an easy 'open path' solution using the path that starts in the top left corner, goes left to right along the top row, right to left along the second row, left to right along the third row, etc, until it goes right to left along the bottom row and ends in the bottom left corner:

+-----+-----+--+-----+--+
| : :B1: : |
+--+--+--+--+--+-----+ |
|W2: : : : |
+..+--+--+--+--+--+--+--+
| : : : |
+-----+-----+-----+--+..+
| : : : |
+..+--+-----+-----+-----+
| : : : |
+--+--+--+--+--+--+--+..+
| : : : :B2|
| +-----+-----+-----+--+
| : : : : |
+--+-----+-----+-----+ |
|W1: : : : |
+--+-----+-----+-----+--+

As I said, it's a small point - not noticeably closer to a solution, just an indication of where one won't find a solution, and just possibly a source of inspiration for further thoughts about the problem.

Gengulphus


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 2 guests