Collection of problems solvable by a coloring argument

Here are some resources for teaching coloring arguments. In the case of two colors, a coloring argument is often called a parity argument.

Here's the ultra-famous "mutilated chessboard problem."

Here's one variation.

And here's another.

Here's a different tiling puzzle, which also requires a parity argument: Is it possible to fit all 35 free hexominoes into a rectangle? Here are the 35 free hexominoes, for reference. And here's the answer.

Here's a problem that can be solved quickly by trial-and-error, which can be followed by this much more difficult extension. Proving impossibility, for this second puzzle, will require a parity proof.


Here's yet another tiling problem solvable by a parity argument: Consider the region pictured below, where the red square indicates a hole in the region. Can it be tiled by 1x2 dominoes?

Solution: The proof can be done by contradiction. Assume that such a configuration is possible. In the above image, consider the blue cells labelled 1, 3, 5, 7, 8, 10. They must be tiled up with the white cells labelled 2, 4, 6, 9, 11. Since there are only 5 white cells and 6 blue cells, this tiling is impossible.


Here are a few more problems.