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?
On
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:
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.
On
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:
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.
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$.
On
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}$$
On
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:
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:
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.
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.