TAOCP 7.2.2.2 Exercise 116

Exercise 116. [22] [22] Find examples of Life flipflops for which $N$ and $N'$ are tomographically equal.

Verified: yes
Solve time: 3m05s

Edit

Solution

Take rows and columns numbered (0,1,2,3), with the top row and leftmost column having index (0). Consider the two finite Life configurations

[ N= \begin{array}{c} .1..
..11
11..
..1. \end{array} \qquad N'= \begin{array}{c} ..1.
1.1.
.1.1
.1.. \end{array}. ]

The live cells of (N) are

[ {(0,1),(1,2),(1,3),(2,0),(2,1),(3,2)}. ]

Applying Conway's Life rule, the cells of (N) that survive are those having two or three live neighbors, and the empty cells that are born are those having exactly three live neighbors. Counting the neighbors of the cells near the pattern gives the next generation

[ {(0,2),(1,0),(1,2),(2,1),(2,3),(3,1)}, ]

which is exactly

[ N'= \begin{array}{c} ..1.
1.1.
.1.1
.1.. \end{array}. ]

Applying the same calculation to (N'), the surviving cells and births give

[ {(0,1),(1,2),(1,3),(2,0),(2,1),(3,2)}, ]

so the second generation is (N). Hence (N) and (N') form a Life flipflop.

It remains to compare their tomographic data. The row sums of (N), from top to bottom, are

[ (1,2,2,1), ]

and the column sums, from left to right, are

[ (1,2,2,1). ]

For (N'), the row sums are also

[ (1,2,2,1), ]

and the column sums are again

[ (1,2,2,1). ]

For diagonals of slope (-1), that is, diagonals with constant (i+j), the nonzero diagonal sums of (N) are obtained from the values of (i+j):

[ (1,1,2,1,1). ]

The same computation for (N') gives

[ (1,1,2,1,1). ]

For diagonals of slope (1), that is, diagonals with constant (i-j), the nonzero diagonal sums of (N) are

[ (1,2,0,2,1), ]

and (N') gives the identical sequence

[ (1,2,0,2,1). ]

Thus the row sums, column sums, and both sets of diagonal sums agree for the two configurations. Therefore (N) and (N') are tomographically equal.

Consequently,

[ \boxed{ N= \begin{array}{c} .1..
..11
11..
..1. \end{array} \qquad N'= \begin{array}{c} ..1.
1.1.
.1.1
.1.. \end{array} } ]

is an example of a Life flipflop whose two states have identical tomographic data. (\square)