In one sentence
Color the squares so that every move has a fixed effect on the colors; then count colors and ignore the details.
First, a guess about the board above:
Predict first
Cut two opposite corners out of an board, leaving squares. dominoes also cover exactly squares. Can they cover the board?
No. A smaller board below makes the reason easy to see, and it is exactly the same reason as for .
Why it can't be covered (a small 4×4 board)
Step 1 / 5- Try it first
Cut out two opposite corners: squares are left, so you need dominoes. Here is one attempt: dominoes placed, but the two squares left are not neighbors, so the th will not fit. What about another placement? No number of tries settles the question.
The power of coloring is that it squeezes “countless placements” down to “are two numbers equal?”. In the four stops below, the colors are painted in different ways.
Stop 1 · A different tile needs a different coloring
Can a board be covered with bars of size ?
Try covering it first. Then try “Checkerboard”: each bar covers black and white squares, and there are of each color, so there is no contradiction. The black-and-white coloring does not help. What about -color diagonals?
Use as many colors as the tile is long, and paint them diagonal by diagonal. Then a bar, whether across or down, covers exactly one square of each color.
Stop 2 · Which square is cut out?
A board has squares. Cut one out, leaving , and try to cover them with bars of size .
Predict first
Cut out the top-left square. Can the remaining squares be covered with bars of size ?
Color with -color diagonals: the squares split into squares of the three colors. To be covered, what is left must be , so the square cut out must have the color that has squares. The top-left square does not.
Below, tap “Move the holes” and put the gap somewhere else. It must pass the test for the -color diagonals in both directions. How many squares pass both?
Each diagonal direction requires you to cut out a square of “the color with one extra”. Only one square, the center, meets both requirements, and with the center cut out the board really can be covered in a pinwheel. The coloring rules out positions; the last one is settled by a construction.
Stop 3 · Walking through the squares
Start at the top-left corner. Each step goes to a square directly above, below, left or right. Visit every square exactly once and finish at the bottom-right corner.
Every step switches color. Visiting squares takes steps, and after an odd number of steps you are always on the opposite color from the start. But two opposite corners have the same color. Here a single step plays the part of a domino, and “one black, one white” becomes “every step switches color”.
Stop 4 · Coloring the lines
The colors do not have to go on squares. Take people. Any two of them either know each other (join them with a red line) or do not (a blue line). There are always people who all know each other, or people none of whom know each other. In the language of graphs: join points in every possible way and color each line red or blue; there is always a triangle whose three sides have the same color.
First try to avoid it yourself. With points you can. What about ?
Why 6 points can't avoid it
Step 1 / 5- Focus on one point
Look only at point . There are lines from it, each red or blue.
What if the two squares cut out have different colors?
Break it
Counterexample lab: remove one condition
Conclusion: The rest can be covered with dominoes ← still true?
Cut two corners on the same side out of a board. With the checkerboard coloring on, one is white and one is black, leaving white and black. Cover it yourself.
Now cut out two opposite corners instead: both squares have the same color, leaving white and black.
However you place them, two black squares are always left over: the white squares run out first. Tap “Ask the computer” and it will tell you that at most dominoes fit.
Practice
A board is colored like a checkerboard, and two opposite corners are cut out. Among the squares left, how much do the numbers of black and white squares differ by?
A classroom has seats, all taken. The teacher asks everyone to move to a seat directly in front of, behind, left of or right of their own. Can it be done? (Answer yes or no.)
Color a board in colors by “the remainder of row number + column number on division by ”. How many squares does the most common color have? (This shows that a board cannot be covered with bars.)
On a grid, start at some square and step to a neighboring square each time. Can you visit every square exactly once and finish by returning to the square you started on? (Answer yes or no.)
Join points in pairs with all lines, and color each line red or blue so that there is no triangle with three sides of the same color. Exactly how many red lines must there be?