Marriage Theorem

Once upon a time, there is a planet with men and women living harmoniously together. On the planet, a man or a woman has neighbors of opposite sex only. They live so well that they only choose one of their neighbors as their husband or wife... However, is it always possible for a man to be able to find a wife or a woman to find a husband? Of course, the answer is simplely no if there are not the same number of men and women. But if there are exactly same number of men and women, what is the answer then?

Well, this marriage problem is wierd, but it is related and helpful to understand another problem, the tiling of squares with dominos.

The following is a 8x8 square with two corners removed. One may ask if the shape can be tiled with dominos. A domino is composed with two adjacent squares. If the corners are present, the answer is obviously positive. However, after removing the two corners, there are 62 squares. Can it be covered completely with 31 dominos? The question at first sight is very difficult, which is generally true for tiling problem due to large number of possible tiling schemes. If fact, if we add an additional property to the identical squares, we may turn the problem into the above marriage probem and find the answer very easily.


Domino


We may color all the squares in two colors alternatingly like a chessboard fasion. See below. If we put a domino anywhere on the board, one square of the domino must be green and the other white. Therefore, if a tiling solution exists, the number of green squares and white squares should be the same. However, we find there are 32 green squares and only 30 white squares. (The alternating pattern is an antiferromagnetic arrangement in the 2-dimensional space and there is a residual net spin though.) So the coloring scheme turns to be crucial to find the negative answer.

Coloring Scheme


However, the coloring method cannot give a definitive answer if we can color the squares alternatingly for the same number of squares. For example, in the following 8x8 square, we remove one square in green and one in white. The resulted shape is obviously tilable. (Though it is maybe difficult to write down all the tiling possibility, we can at least find a few.)


However, in the same 8x8 square, we remove two whites and two greens and obtain the pattern shown below (the black square is one of the holes). There is no way to tile the upper left corner with a domino, for which the corner is an isolated square.


There are a lot of more to say about tiling and marriage theorem. But so far, i only understand little of them.