Hi Frank!

This week I think I solved a problem that you and your students might
enjoy. Although the outcome is not in doubt (I hope), I'm writing to you
because (a) as I say, I think you'll enjoy looking at it, and (b) I hope
you find a proof that's shorter than mine, so that I can use it in TAOCP.

The problem concerns what I call "pure flipflops", which were first
discovered by Bill Gosper about 1971 and communicated by him to
Martin Gardner. Martin most likely sent a copy of Bill's letter
to John Conway, because Gosper's most exotic pure flipflop is illustrated
in Figure 6 of Chapter 25 of Winning Ways.

A pure flipflop is a two-cycle in the Game of Life for which every
live cell dies at every generation, only to be reincarnated again
by its offspring. But that high-level description isn't necessary;
all you need are the following elementary rules:

(1) Every cell of the plane is either 0 or A or B. I assume that
only finitely many cells are A or B.

(2) Each cell has eight neighbors (its king-neighbors). We let
sA and sB denote the number of neighbors of types A and B, respectively.

(3) Every A cell has sA != 2, sA != 3, and sB = 3. [This means it
dies, according to the rules of Life, then it is reborn again.]

(4) Every B cell has sB != 2, sB != 3, and sA = 3.

(5) Every 0 cell has sA != 3 and sB != 3. [So it's always dead.]

Playing with my computer I discovered to my astonishment that
the motifs of pure flipflops go well beyond those that Gosper
had discovered in that Figure 6. Some of the patterns are quite
beautiful, in fact, although you need to go to somewhat large
grids before you can see the most interesting ones.

(My book will recommend that these patterns be used in three-colored
floor tilings, in rooms used by hackers!)

Based on a couple days' worth of experiments, I conjectured that
the following is true:

(3') Every A cell has sA <= 1 and sB = 3.

(4') Every B cell has sB <= 1 and sA = 3.

This conjecture fails for infinite patterns. But, several
times, I thought I'd found a proof for finite ones. Then, several
more times, I realized that my proof had a gaping hole, and
I spent a few hours plugging that hole.

I hate to admit how many iterations I needed before converging
on what I truly do believe is an airtight proof. Still, all the
while, I was certainly having great fun. (And thinking about
you and tatami mats, although I don't think the problems
are related.)

Have a great summer! -- Don