Incomplete proof, please help!
Posted: June 18th, 2015, 11:27 am
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?
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?