Matthew Cook 20 Sep 98


The reasoning goes like this:
Suppose you can divide it into 5 or more stable subsets.
Enlarge each island by half a cell, so that islands can touch each other.
(Any cell with no live neighbors remains "international waters".)
Call each group of contiguous islands of the same set a "country".

Now we have a map that the four-color theorem applies to.
We can use the four-color theorem to redivide the countries into just
four sets.

This means that independent stability will be preserved, since where
two adjacent islands used to be in the same set, they will still be in
the same set, and where they used to be in different sets, they will
still be in different sets.

Similarly, where three islands meet, their set-sameness will be preserved.

But where four countries meet at a point, there might be trouble:

            A A . B B
            A A . B B
            . . . . .
            C C . D D
            C C . D D

In this case, the four-color theorem cannot promise to keep these
countries all different.  It can only promise to keep adjacent
countries different.  So it might come back as:

        1 1 . 2 2                         1 1 . 2 2
        1 1 . 2 2                         1 1 . 2 2
        . . . . .        or even          . . . . .
        2 2 . 3 3                         2 2 . 1 1
        2 2 . 3 3                         2 2 . 1 1

Luckily for us, each of these possibilities happens to preserve the
independent stability needed for the pseudo-still-life definition,
so in the end the four-color theorem is indeed sufficient for proving
that four subsets is all we ever need.