Parity problems arise in some tiling problems. These are instances where the area to be tiled and the pieces can all be colored in a regularly repeating fashion (like a checkerboard) and the result is that some tilings are proved impossible, or limited in certain ways. Often, but not always, these are two-parity issues (odd or even issues, or colorings using two colors).

The classic parity problem is this one:
Take a checkerboard, and cut off two opposite corners. Tile it with 31 "dominoes", 1x2 rectangles which can exactly cover two adjacent squares on the checkerboard, or prove impossible.

The impossibility proof comes from a parity argument. Color the checkerboard alternately white and black in the usual fashion. Each domino must cover one white and one black square, because any two adjacent squares on the board are of opposite color. However, the board contains 30 squares of one color and 32 squares of the other, so these dominoes can never tile it.

Another more generalized parity issue arises in the problem of tiling a square with smaller squares. In this case, if the overall square is of an odd length, the number of odd-sized smaller squares used to tile it must be one more than a multiple of four (or 1 mod 4, in modular arithmetic).

The proof is as follows: The area of any odd square is congruent to 1 mod 4, and the area of any even square is congruent to 0 mod 4 (a multiple of 4). Thus the total area of a set of squares is congruent to the number of odd squares in the set, mod 4. In order for this to match the possible area of one odd square, the number of odd squares must be congruent to 1 mod 4.

A secondary result is that at least 5 odd squares are required to tile an odd square with smaller squares. Besides the overall area constraint, each row and column in the odd square must contain parts of an odd number of odd squares, since it contains a segment of each square equal to its length. If you only have one odd square, it would have to be in every row and every column, and thus would have to be the same as the large square itself, but the degenerate solution of tiling a square with the same square is excluded.

Log in or register to write something here or to contact authors.