Incomplete proof, please help!

[Kiran]

To prove that the block is the only polyomino still life I will consider a general polyomino and prove that it must either be a block or not a still life.
A still polyomino, as well as any other finite pattern, must have a well defined minimal building box which must have a non empty top row.
This top row may not have any groups of more then two consecutive cells, otherwise an outside cell would have 3 neighbors.

If there is a lonely cell a on the top row it must be connected to a cell directly below it b and, to give a two neighbors, another cell c diagonally below a.
0 0 0
0 a 0
? b c
To prevent birth of the cell above c another cell e or d is needed (but not both because c would be overpopulated).
0 0 0 0
0 a 0 d
? b c e
If d all cells adjacent to c are excluded and the only possible extension (necessary to connect to d) is to the left of b, excluding all cells adjacent to b.
0 0 0 0
0 a 0 d
f b c 0
0 0 0 0
To prevent birth left of a the cell left of f is necessary (the cell above that would isolate the central T-tetromino), this cell gives f 3 neighbors.
0 0 0 0 0
0 0 a 0 d
g f b c 0
0 0 0 0 0
The only possible extention:
0 0 0 0 0 0
? 0 0 a 0 d
h g f b c 0
? 0 0 0 0 0
The cell above h is necessary to prevent birth above g, excluding the cell below h (g would be overpopulated.)
0 0 0 0 0 0
i 0 0 a 0 d
h g f b c 0
0 0 0 0 0 0
Now the column to the left of h is in the same situation as the column f is on, forcing an unstabilizable infinite line of tables.
If e is used in-staid of d the same situation occurs with a line of tables that cannot be linked downward to stabilize it.
Therefore if the top row contains a "lonely" cell the polyemeno cannot be a still life.

If there are runs of two in the top row let's call a live cell of the top row a and the cell directly to the right b.
First consider the case where b is live, since the domino is not a still life, another cell must link to a or b or both from below (not the side because that would make a group of 3).
0 0 0 0
0 a b 0
? c d ?
If both are linked the result is a block and no more cells can be attached because every cell already has 3 neighbors.
If 1 is linked (lets assume a) a pre-block results and more cells must be attached to c (e or f but not both because c would be overpopulated.)
0 0 0 0
0 a b 0
e c 0 ?
? f ? ?
If e is live then the cell left of e is the only extension (the cell below e would overpopulate c and the S-tetromino is unstable without an extension.)
0 0 0 0 0
? 0 a b 0
g e c 0 ?
? 0 0 0 ?
The S-pentomino is also unstable and can only be extended to the cell left of g (the cells above and below g would overpopulate e.)
0 0 0 0 0 0
? 0 0 a b 0
h g e c 0 ?
? 0 0 0 0 ?
To prevent birth of the cell above g a cell above h is required thus giving g 3 neighbors and excluding the cell below h.
0 0 0 0 0 0
i 0 0 a b 0
h g e c 0 ?
0 0 0 0 0 ?
If a stabilization is attempted by adding a cell left of i then no further addition is possible because c, e, g and h already have 3 neighbors and the other two possible extensions would cause groups of 3 cells on the top row (no cells are allowed above the row a is on since it is assumed to be the top row) and an unstable pattern results.
0 0 0 0 0 0 0
0 i 0 0 a b 0
? h g e c 0 ?
? 0 0 0 0 0 ?
Thus if e is used and not f (and not a block either) the top row must contain a cell (i) in the top row with no adjacent cells on that row and because of the first case no still life results.
Now what if f?
All other cells next to c are excluded to prevent overpopulation.
0 0 0 0
0 a b 0
0 c 0 ?
0 f 0 ?
Since the L-tetromino is unstable it must be extended in the only possible direction.
0 0 0 0
0 a b 0
0 c 0 ?
0 f 0 ?
? g ? ?

Now what?
Is there some way to finish my attempt or do other still polyominos exist?

[Nathaniel]

The argument looks good so far, however it is indeed going to have to change a bit to proceed much farther. The problem is that you can continue "snaking around" forever(?), so this type of argument will never end. For example, you can continue extending your polyomino like this:

Code: Select all

0 0 0 0
0 a b 0 0 0
0 c 0 v w x
0 f 0 u 0 0
0 g 0 t 0 0
0 h 0 s r 0
0 i 0 0 q 0
0 j 0 0 p 0
0 k l m n 0

And then just continuing to snake around to overpopulate dead cells that currently have 3 alive neighbours (such as on the left and bottom edges of the picture above).

Your argument shows that a polyomino still life must start with an L-pentomino on its top edge. By symmetry, it must also have an L-pentomino somewhere on its left edge, right edge, and bottom edge. It seems like we should be able to use this to prevent the type of "snaking around" I described above (since every "snake" will have just two endpoints, but it apparently needs to have an endpoint on all four sides).

[Kiran]

That may be a strong argument because branches are impossible:
0 0 1
1 1 1
0 0 1
Also, two opposite corners connected by a wiggly snake is impossible because the L-pentomino cannot be fit into a corner without causing an infinite table.

[dvgrn]

I did a little bit of searching and found a reference to an October 1992 proof that the block is the only stable polyomino, by Rich Schroeppel. But it's just a reference -- the quote from Rich was "My proof is relatively easy, so it's unlikely to be original. In fact, it could reasonably be set as a textbook exercise." Also that it was "an open question from 1970".

This lends an aura of Fermat's-Last-Theorem-like mystery to the whole question. Can anyone locate details of the actual proof?

Or if it's a reasonable textbook exercise, can we assume that the "must have a N, S, E, and W end, but can't have any junctions, so any such still life must be made up of at least two polyominoes" argument is as short and easy as it gets?

[codeholic]

A counterexample

Code: Select all

x = 21, y = 21, rule = B3/S23:K21,21*
8$o2bo2bo2bo2bo2bo2bo$21o2$21o$o2bo2bo2bo2bo2bo2bo!

[The Turtle]

1. Each edge of the still life must start with an L tetromino.

2. Only snaking is allowed, and no branches of length two or more can exist. (Is a branch of length 1 allowed? Or not?)
Example:

Code: Select all

ooooooo
     o

versus

ooooooo
     ?
     o

3. There must be at least 4 L's on each side. (unless the polyomino is a block)

4. The L's cannot be connected because branching is needed and the maximum branch is of length 1 (not enough for the four cells).

5. Two L's are not allowed on the same side because more branching is needed.

6. The only polyomino still life is a block

I'm pretty much stating what everyone else stated.
My questions are: Is this reasoning correct? Are there any missed exceptions?