7
$\begingroup$

We have a $8\times 8$ board, colored with two colors like a typical chessboard. Now, we remove two squares of different colour. Is it possible to cover the new board with two-color pieces (i.e. domino pieces)?

I think we can, as after the removal of the two squares, we are left with $64-2=62$ squares with $31$ squares of each colour, and - since the domino piece covers two colours - we can cover the new board with domino pieces.

But how should one justify it mathematically?

$\endgroup$
8
  • 4
    $\begingroup$ It's possible to remove four squares, two of each color, and not cover the remaining with dominos, because the new set is disconnected. So you need to know more than that there are 31 of each color. $\endgroup$ Oct 15 '16 at 16:49
  • $\begingroup$ Your constraints are valid. But there must be more constraints. Such that the colours alternate on the board, that dominos are made of two different colours, next to each other. Then the shape of the board. $\endgroup$
    – mvw
    Oct 15 '16 at 17:05
  • 2
    $\begingroup$ @mvw "like a typical chessboard" should cover all of that. $\endgroup$
    – JMoravitz
    Oct 15 '16 at 17:11
  • $\begingroup$ @JMoravitz That was not my point. The problem is clear. It is about the proof attempt. hetajr just cared about a subset of all constraints that play a role here. $\endgroup$
    – mvw
    Oct 15 '16 at 17:13
  • $\begingroup$ @ThomasAndrews Ah cutting off two corners, leaving single corner stones. $\endgroup$
    – mvw
    Oct 15 '16 at 17:23
8
$\begingroup$

Assume without loss of generality that the two squares to be removed are in different rows. (Otherwise turn the board 90°).

First cover the board in horizontal dominoes, and connect the two squares by a zig-zag line like this:

diagram here

which follows the rule that if the line goes through one end of a domino, it immediately connects to another end. (The requirement that the two squares have different colors ensure that this will be true of the end of the path if only we start out in the right direction for this to hold at the beginning). Now you can flip dominoes along the zig-zag line to produce a covering that avoids the two squares.

another diagram here


With a bit of (easy) special-casing for the same-row case, this strategy can be extended to any size board as long as one of the side lengths is even and the other is $\ge 2$.

$\endgroup$
4
  • $\begingroup$ I do not get the flipping. But it seems clear the length of the zig zag line is a multiple of two, as is the reduced line, so it can be covered. $\endgroup$
    – mvw
    Oct 15 '16 at 17:31
  • $\begingroup$ @mvw: Initially every other of the square boundaries crossed by the red line was covered by a domino. By "flipping" I mean to instead cover the other half of the boundaries by dominos. $\endgroup$ Oct 15 '16 at 17:36
  • $\begingroup$ weren't you lucky that the top and bottom part had an even number of squares ? $\endgroup$
    – mercio
    Oct 16 '16 at 13:23
  • $\begingroup$ @mercio: If the top endpoint had been at an even column, I would just have started going left instead of right. This means that the zig-zag line would always enter each of the original dominoes at the end that has the same color as the top endpoint, so the bottom endpoint will always be reached at the end of a domino. $\endgroup$ Oct 16 '16 at 13:33
5
$\begingroup$

From a graph theory point of view, this can be seen as a "matching problem" on a bipartite graph.

The nodes of the graph are the squares remaining.

Two nodes have an edge in the graph if the squares are neighbors - that is, if the two squares can be covered by a single domino.

Obviously, in any edge, one square is white, the other black, hence the "bipartite" nature of this graph.

So you are seeking to show there is a perfect matching for any such graph.

There is a general theorem about when there is a perfect matching for a bipartite graph, called Hall's Theorem or Hall's Marriage Theorem. It is possibly overkill for this question - induction is likely the better approach.


Per the discussion on Henning's answer, it is actually possible to prove your theorem directly using a "Hamilton cycle" on the chess board.

Consider the loop path on the board:

$$\begin{matrix}1&2&3&4&5&6&7&8\\ 64&15&14&13&12&11&10&9\\ 63&16&17&18&19&20&21&22\\ 62&29&28&27&26&25&24&23\\ 61&30&31&32&33&34&35&36\\ 60&43&42&41&40&39&38&37\\ 59&44&45&46&47&48&49&50\\ 58&57&56&55&54&53&52&51 \end{matrix}$$

So we have walked in a circle, and, if the upper left is black, then we have that odd numbers on black and the even numbers on white.

If we unwind this, and consider it 64 beads in a circle, alternating black and white, then if we remove/cut away one black and one white bead, we are either left with one string of 62 beads alternating black/white, which lets us cover those with dominos, or two seperate strings.

With two strings, here is the key: because we cut away one black and one white bead, those two strands are of even length.

For example, if we removed the square at 12 and the square at 23, then we could get the domino placement: $$(13,14),(15,16),(17,18),(19,20),(21,22), \\(24,25),\dots,(62,63),(64,1),(2,3),(4,5),(6,7),(8,9),(10,11).$$

This can be generalized as: "If a bipartite graph has a Hamiltonian cycle, then if you remove one node from each of the parts, you can still get a perfect matching."

In particular, this argument works for any $2n\times m$ board, because we can get a "King's cycle tour" on any such board.

For example, a $3\times 4$ board:

$$\begin{matrix} 1 & 2& 3&4\\ 12& 9& 8&5\\ 11&10& 7&6 \end{matrix}$$

$\endgroup$
4
  • $\begingroup$ (+1) Interesting approach. In this framework, we just need to check that the hypothesis of Hall's theorem are met, i.e. that for any subset of white (or black) squares in the truncated chessboard, their neighbourhood has a larger cardinality, and that is clearly true. $\endgroup$ Oct 15 '16 at 17:46
  • $\begingroup$ (on the other hand, induction is just the usual way for proving Hall's theorem) $\endgroup$ Oct 15 '16 at 17:54
  • $\begingroup$ Hmm, yes, I suppose you could prove that for a subset of $k$ white squares on the uncut board, with $0<k<32$, the set of neighboring black squares has at least $k+1$ elements, then you can apply Hall's theorem to the cut board. @JackD'Aurizio $\endgroup$ Oct 15 '16 at 18:31
  • $\begingroup$ And that can indeed be proved. (Posted as a separate answer so I can show diagrams). @JackD'Aurizio too. $\endgroup$ Oct 15 '16 at 20:50
4
$\begingroup$

Hint: A promising strategy is to prove that the claim

If we remove two opposite-colored squares from a $2m\times 2m$ chessboard,
we may tile the remaining part with $2\times 1$ dominoes.

by induction on $m$. The case $m=1$ is trivial. Assume that the claim holds for some $m\geq 1$ and consider a $(2m+2)\times (2m+2)$ chessboard. If both the removed squares do not lie on the boundary of the chessboard, there is nothing to prove. Hence we may assume that at least one of the removed squares lies on the boundary. And we may also start tiling by following a spiral, starting next to the removed square on the boundary:

enter image description here

Another interesting idea is just to place $31$ non-overlapping dominoes on a $8\times 8$ chessboard and start playing Sokoban with the placed dominoes, in order to free the wanted squares.

$\endgroup$
3
  • $\begingroup$ I like this one the best so far. Still thinking about it. $\endgroup$
    – mvw
    Oct 15 '16 at 17:19
  • 1
    $\begingroup$ You might be able to prove this form $2m\times n$ for any $n>1$, which makes it easier to do the induction. $\endgroup$ Oct 15 '16 at 17:42
  • $\begingroup$ @ThomasAndrews: true. Interesting remark, thanks. $\endgroup$ Oct 15 '16 at 17:53
2
$\begingroup$

Completing an approach suggested by Thomas Andrews, if we can show that on the complete chessboard any proper subset of the white squares have more black neighbors than it has members, then Hall's marriage theorem will apply to the chessboard with two squares erased.

Suppose therefore, that a proper subset of the white squares are given. Since the red and green lines in the following diagram connect all the white squares, there will be at least one red or green line that goes from a square in the subset to a square outside of it:

diagram goes here

Assume without loss of generality that there is a red line joining a square in the subset to a square outside the subset. (Otherwise mirror everything around the white diagonal).

Now pair up each white square with the black neighbor it is connected to by a blue line in this diagram:

diagram goes here

This gives one neighboring black square for each white square. However the white square with a diagonal-partner that is not selected is additionally neighbor to the non-selected square's black partner which is not otherwise used.

So, as desired, our set of white squares has more black neighbors in total than there are white squares in the set.

$\endgroup$
5
  • $\begingroup$ Very nice! I couldn't quite find that zig-zag argument while trying to find the "extra" black square. $\endgroup$ Oct 15 '16 at 21:39
  • 1
    $\begingroup$ @ThomasAndrews: Actually this is, on further thought, still more complicated than it needs to be. Just fix a Hamiltonian circuit on the board (necessarily with alternating white and black squares) and then just count neighbors along that circuit for each run of selected white squares. $\endgroup$ Oct 15 '16 at 22:47
  • 1
    $\begingroup$ of course, once you have a Hamiltonian circuit, you actually don't need Hall's theorem. Just remove your two nodes, and you get one or two paths, both of even lengths. $\endgroup$ Oct 15 '16 at 23:21
  • $\begingroup$ @ThomasAndrews: Indeed. I would update my main answer, except I would have to make new diagrams ... $\endgroup$ Oct 15 '16 at 23:22
  • $\begingroup$ Okay, I updated my answer with the non-Hall Hamiltonian cycle answer. $\endgroup$ Oct 16 '16 at 12:57
0
$\begingroup$

Yes.

Consider the board initially covered with dominoes. After the two squares have been removed, the board has two holes.

If the two holes were in the same row, slide the dominoes between the holes until one of the holes is filled. This will leave two adjacent holes that can be covered by a domino.

If the holes are in different rows, slide dominoes from the lower row to the upper row up until one of the holes is filled. That leaves the lower row with two holes which can be filled as described above.

If the two rows are adjacent, slide the upper row left or right until its hole is filled and the hole has moved above the hole in the next row. This can be filled by a domino.

$\endgroup$
3
  • 1
    $\begingroup$ How does this answer make use of the information that the holes are on squares of different colour? $\endgroup$
    – HTFB
    Oct 15 '16 at 17:02
  • 1
    $\begingroup$ "Slide dominoes" won't work if the holes are in column 2 and 3 of the same row. $\endgroup$ Oct 15 '16 at 17:11
  • 2
    $\begingroup$ I think this answer is wrong because if the holes are of the same colour, then it should not work. $\endgroup$ Oct 15 '16 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.