ConwayLife.com

Forums for Conway's Game of Life
https://conwaylife.com/forums/

Still life puzzles

https://conwaylife.com/forums/viewtopic.php?t=2923

Page 1 of 2

Still life puzzles

Posted: June 25th, 2017, 1:22 pm
by wwei23
These two have left me confused no matter what I try.
One (None exist): Do any still lifes exist from 9 to 19 cells so that every living cell has exactly two living neighbors and if not, then why(I've also apgsearched and turned up empty-handed.)?
And two (None exist): Other than some agars, is the block the only still life where every living cell has exactly three neighbors? If so, then why?

Re: Still life puzzles

Posted: June 25th, 2017, 2:00 pm
by muzik
I'm pretty sure that the block is the only finite pattern at all with very cell having exactly 3 neighbours.

Re: Still life puzzles

Posted: June 25th, 2017, 2:58 pm
by BlinkerSpawn
muzik wrote:I'm pretty sure that the block is the only finite pattern at all with very cell having exactly 3 neighbours.
I also believe that the only stable patterns with every cell having 3 neighbors consist exclusively of blocks.
Here I will attempt to construct a pattern with every cell having 3 neighbors and containing no blocks.
Set your coordinate system so that the lower left corner of the pattern's bounding box is at (0,0), with coordinates increasing going up and to the right:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$D$D$10D!
Assume (0,0) is ON.
For the cell to have 3 live neighbors, (1,0), (0,1), and (1,0) must be ON, but then the pattern contains a block and is invalid, so (0,0) must be OFF:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$D$2A$CA8D!
Let's say (1,0) is ON instead.
There are four possible neighbors for (1,0): (0,1), (1,1), (2,1), and (2,0), but one of these must be (0,1) because the other three neighbors constitute a block. In addition, allowing (1,1) to be ON creates B3a at (0,0) so it is OFF and the other two neighbors must therefore be ON. Similar logic applies to (0,1), resulting in a ship:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$2C$C.C$B2C7D!
But (2,0) has two neighbors, and giving it a third causes (2,1) to have four neighbors and die, so this solution is also unworkable, and neither (1,0) nor (0,1) can be on in any solution. (This logic is reflection-invariant and so applies to both cases)
Let's force (2,0) to be ON, then.
By identical logic to the above we can immediately force these cells ON:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$D$BC.C$2B2C6D!
To prevent the contradiction in the previous case, though, (2,2) must stay OFF, forcing (1,1)'s two neighbors to be (2,1) and (2,0), creating B3a on (0,1). Therefore, (2,0) and (0,2) don't work either:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$2C$BC.C$2B2C6D!
Similarly, (3,0) creates this:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$B2C$B.C.C$3B2C5D!
(4,0) doesn't work:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$B$B3C$B2.C.C$4B2C4D!
This is the only way (5,0) can be done without creating birth at (2,1) or death at (3,2), but (1,1) and (1,2) are still unrescuable:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$B$B$B4C$BC2.C.C$5B2C3D!
And (6,0) has to be one of these but I don't know how to carry the logic past that:

Code: Select all

x = 30, y = 10, rule = LifeHistory
D19.D$D19.D$D19.D$D19.D$B19.B$B19.B$B19.B$B.4C14.B5C$B2C2.C.C12.B.C2.
C.C$6B2C2D10.6B2C2D!
I'm pretty sure some sort of proof-by-induction is possible along these lines.
If I could prove in each step that not just the end cells but each successive diagonal must be clear then the solution should just reduce to showing that each attempt to follow the instructions just creates the next level of ship and the proof would trivially follow from that and the logic used above.

Re: Still life puzzles

Posted: June 25th, 2017, 3:34 pm
by muzik
If such a pattern with exclusively 3 neighbours did actually exist, it would have to be big:

https://catagolue.appspot.com/census/bs3/C1

Re: Still life puzzles

Posted: June 25th, 2017, 4:23 pm
by wwei23
A pattern can contain a block, but it can't be JUST blocks.

Re: Still life puzzles

Posted: June 25th, 2017, 4:35 pm
by drc
I mean there's still an infinitely long shiptie or infinitely long barge, but I guess those wouldn't count.

EDIT: Also I don't know if that's what you meant by 'agars'. I was picturing something like infinite chicken wire:

Code: Select all

x = 10, y = 4, rule = B3/S23
2o2b2o2b2o$2b2o2b2o$2o2b2o2b2o$2b2o2b2o!

Re: Still life puzzles

Posted: June 25th, 2017, 6:49 pm
by wwei23
The still life must be finite.

Re: Still life puzzles

Posted: June 27th, 2017, 9:51 am
by wwei23
I found a potential induction coil. Now we just need to stabilize it.

Code: Select all

x = 5, y = 10, rule = B3/S23
2bo$b3o$o3bo$2ob2o$bobo$bobo$2ob2o$o3bo$b3o$2bo!
Edit:
Never mind:
Because all the living cells of the seed have three living neighbors, no cells can be on adjacent to any of them. These cells are shown in blue:

Code: Select all

x = 7, y = 12, rule = LifeHistory
2.3B$.2BA2B$2B3A2B$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$BA3BAB$2B3A
2B$.2BA2B$2.3B!
Therefore, none of the red cells can be on, because they will cause a birth at gray. But all other surrounding cells except for the seed cells are blue, so the red cells must be off:

Code: Select all

x = 7, y = 12, rule = LifeHistory
2.3B$D2BA2BD$BF3AFB$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$BA3BAB$BF
3AFB$D2BA2BD$2.3B!
So all cells forced off are shown in blue:

Code: Select all

x = 7, y = 12, rule = LifeHistory
2.3B$3BA3B$2B3A2B$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$BA3BAB$2B3A
2B$3BA3B$2.3B!
The red cells have three on neighbors, four forced off neighbors, and one unset neighbor. To prevent a birth at red, the unset neighbor must be forced on:

Code: Select all

x = 7, y = 12, rule = LifeHistory
.A3BA$2BDAD2B$2B3A2B$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$BA3BAB$2B
3A2B$2BDAD2B$.A3BA!
So this is the pattern so far:

Code: Select all

x = 7, y = 12, rule = LifeHistory
.A3BA$3BA3B$2B3A2B$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$BA3BAB$2B3A
2B$3BA3B$.A3BA!
Because the red cells would cause a birth at gray, and all other neighbors are either seed cells, cells forced on, or blue, the red cells must be off:

Code: Select all

x = 7, y = 12, rule = LifeHistory
DA3BAD$BFBABFB$2B3A2B$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$BA3BAB$
2B3A2B$BFBABFB$DA3BAD!
All blue cells must be off:

Code: Select all

x = 7, y = 12, rule = LifeHistory
BA3BAB$3BA3B$2B3A2B$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$BA3BAB$2B
3A2B$3BA3B$BA3BAB!
Because each of the gray cells are on, they must have three living neighbors:

Code: Select all

x = 7, y = 12, rule = LifeHistory
BF3BFB$3BA3B$2B3A2B$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$BA3BAB$2B
3A2B$3BA3B$BF3BFB!
And they have exactly three unset neighbors each, in red:

Code: Select all

x = 7, y = 14, rule = LifeHistory
3D.3D$BA3BAB$3BA3B$2B3A2B$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$BA3B
AB$2B3A2B$3BA3B$BA3BAB$3D.3D!
So we can force them to be on:

Code: Select all

x = 7, y = 14, rule = LifeHistory
3A.3A$BA3BAB$3BA3B$2B3A2B$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$BA3B
AB$2B3A2B$3BA3B$BA3BAB$3A.3A!
The red cells are off, with three on neighbors:

Code: Select all

x = 7, y = 14, rule = LifeHistory
3A.3A$BABDBAB$3BA3B$2B3A2B$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$BA
3BAB$2B3A2B$3BA3B$BABDBAB$3A.3A!
And one gray unset neighbor:

Code: Select all

x = 7, y = 14, rule = LifeHistory
3AF3A$BABDBAB$3BA3B$2B3A2B$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$BA
3BAB$2B3A2B$3BA3B$BABDBAB$3AF3A!
To prevent a birth at red, the gray cells must be on:

Code: Select all

x = 7, y = 14, rule = LifeHistory
7A$BABDBAB$3BA3B$2B3A2B$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$BA3BAB
$2B3A2B$3BA3B$BABDBAB$7A!
Because some forced on cells have three living neighbors, none of their surrounding neighbors can be on, or else they die:

Code: Select all

x = 7, y = 16, rule = LifeHistory
7B$7A$BA3BAB$3BA3B$2B3A2B$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$BA3B
AB$2B3A2B$3BA3B$BA3BAB$7A$7B!
But that leaves two forced on cells shown in red that have only two neighbors. And because of their surrounding forced on cells that have three, they have no unset neighbors to be forced on:

Code: Select all

x = 7, y = 16, rule = LifeHistory
7B$3AD3A$BA3BAB$3BA3B$2B3A2B$BA3BAB$B2AB2AB$2BABA2B$2BABA2B$B2AB2AB$B
A3BAB$2B3A2B$3BA3B$BA3BAB$3AD3A$7B!
And therefore the initial pattern, the seed, cannot be stabilized.

Re: Still life puzzles

Posted: June 29th, 2017, 1:53 am
by gameoflifeboy
wwei23 wrote:Do any still lifes exist from 9 to 19 cells so that every living cell has exactly two living neighbors and if not, then why?
I've been searching B3/S2 for years to try to answer this. I'm already pretty sure the answer is "no", because the only available islands seem to be preblocks and rings of cells joined orthogonally or diagonally. I could find three at 20 cells though:

Code: Select all

x = 22, y = 17, rule = B3/S23
16bo$15bobo$4bo10bobo2bo$3bobo6b2obobobobo$3bobo6bo2bobo2bo$b2o3b2o6bo
2bo$o7bo6b2o$b2o3b2o$3bobo$3bobo$4bo10b2o$14bo2bo$14bobo2bo$11b2obobob
2o$11bo2bobo$13bo2bo$14b2o!

Re: Still life puzzles

Posted: July 2nd, 2017, 12:32 pm
by wwei23

Code: Select all

x = 290, y = 45, rule = LifeHistory
204.2A$203.A2.A$203.A.A2.A$200.2A.A.A.2A$200.A2.A.A$202.A2.A$203.2A
37.2A$241.A2.A$242.2A$204.A$203.A.A34.4A$203.A.A2.A30.A4.A$200.2A.A.A
.A.A30.4A$200.A2.A.A2.A$202.A2.A34.2A$203.2A34.A2.A$240.2A2$203.A36.
2A$202.A.A34.A2.A$90.D3.D5.D.D7.3D7.3D7.3D17.3D7.3D7.3D7.D.D7.3D10.A
36.2A$90.2D.2D5.D.D7.D10.D8.D19.D.D8.D8.D.D7.D.D7.D$90.D.D.D5.3D7.3D
8.D8.3D17.2D9.D8.D.D7.D.D7.3D8.5A34.4A$90.D3.D6.D10.D8.D8.D19.D.D8.D
8.D.D7.D.D9.D7.A5.A32.A4.A$90.D3.D6.D8.3D8.D8.3D17.D.D7.3D7.3D7.3D7.
3D8.5A34.4A2$203.A36.2A$202.A.A34.A2.A$203.A36.2A$244.A19.2A18.2A$
204.A19.2A17.A.A17.A2.A16.A2.A$203.A.A17.A2.A16.A.A18.A2.A15.A2.A$
203.A.A18.A2.A13.2A3.2A13.3A4.A12.2A4.2A$201.2A3.2A13.3A4.A11.A7.A11.
A8.A10.A8.A$90.4D46.3D47.3D7.A7.A11.A5.A.A11.A7.A12.A5.A.A10.A8.A$61.
A4.2A3.A9.2A3.A3.D49.D.D47.D.D8.2A3.2A13.A3.A.A13.2A3.2A14.A3.A.A12.
2A4.2A$41.A18.A.A4.A2.A.A7.A2.A.A.A2.D.2D46.3D47.3D10.A.A16.A2.A17.A.
A17.A2.A16.A2.A$40.A.A17.A.A2.A4.A2.A6.A2.A.A2.A.D2.D46.D.D47.D12.A.A
17.A.A17.A.A18.A.A16.A2.A$41.A19.A3.2A4.2A8.2A3.A.A.4D46.D.D47.D13.A
19.A19.A20.A18.2A$87.A$3B7.2B8.3B7.3B7.B.B7.3B7.3B7.3B7.3B7.3B7.2B2.
3B3.2B2.2B4.2B2.3B3.2B2.3B3.2B2.B.B3.2B2.3B3.2B2.3B3.2B2.3B3.2B2.3B3.
2B2.3B3.3B.3B13.3B.2B14.3B.3B13.3B.3B13.3B.B.B$B.B8.B10.B9.B7.B.B7.B
9.B11.B7.B.B7.B.B8.B2.B.B4.B3.B5.B4.B4.B4.B4.B2.B.B4.B2.B6.B2.B6.B4.B
4.B2.B.B4.B2.B.B5.B.B.B15.B2.B16.B3.B15.B3.B15.B.B.B$B.B8.B8.3B7.3B7.
3B7.3B7.3B9.B7.3B7.3B8.B2.B.B4.B3.B5.B2.3B4.B2.3B4.B2.3B4.B2.3B4.B2.
3B4.B4.B4.B2.3B4.B2.3B3.3B.B.B13.3B2.B14.3B.3B13.3B.3B13.3B.3B$B.B8.B
8.B11.B9.B9.B7.B.B9.B7.B.B9.B8.B2.B.B4.B3.B5.B2.B6.B4.B4.B4.B4.B4.B4.
B2.B.B4.B4.B4.B2.B.B4.B4.B3.B3.B.B13.B4.B14.B3.B15.B5.B13.B5.B$3B7.3B
7.3B7.3B9.B7.3B7.3B9.B7.3B7.3B7.3B.3B3.3B.3B3.3B.3B3.3B.3B3.3B3.B3.3B
.3B3.3B.3B3.3B3.B3.3B.3B3.3B.3B3.3B.3B13.3B.3B13.3B.3B13.3B.3B13.3B3.
B!
22 cells:

Code: Select all

x = 46, y = 13, rule = LifeHistory
3.A$2.A.A6.2A10.2A6.2A10.2A$2.A.A5.A2.A8.A2.A4.A2.A8.A2.A$3.A7.2A10.
2A6.2A10.2A2$.5A5.4A6.4A6.4A6.4A$A5.A3.A4.A4.A4.A4.A4.A4.A4.A$.5A5.4A
6.4A6.4A6.4A2$3.A7.2A8.2A8.2A8.2A$2.A.A6.A9.A10.A9.A$3.A9.A9.A6.A9.A$
12.2A8.2A6.2A8.2A!
23 cell still life:

Code: Select all

x = 7, y = 12, rule = LifeHistory
3.A$2.A.A$3.A2$.5A$A5.A$.5A2$3.A$2.A.A$.A2.A$2.2A!
24 cells:

Code: Select all

x = 68, y = 89, rule = LifeHistory
2.A$.A.A9.A18.2A8.2A9.2A8.2A$.A2.A7.A.A16.A2.A6.A2.A7.A2.A6.A2.A$2.A.
A7.A.A17.A2.A6.A2.A7.A2.A6.A2.A$3.A9.A19.2A8.2A9.2A8.2A2$.5A5.5A17.4A
6.4A5.4A6.4A$A5.A3.A5.A15.A4.A4.A4.A3.A4.A4.A4.A$.5A5.5A17.4A6.4A5.4A
6.4A2$3.A9.A19.2A8.2A7.2A8.2A$2.A.A7.A.A19.A8.A9.A8.A$3.A8.A.A17.A12.
A5.A12.A$13.A18.2A10.2A5.2A10.2A3$33.2A8.2A10.2A8.2A$32.A2.A6.A2.A8.A
2.A6.A2.A$31.A2.A6.A2.A8.A2.A6.A2.A$32.2A8.2A10.2A8.2A2$32.4A6.4A6.4A
6.4A$31.A4.A4.A4.A4.A4.A4.A4.A$32.4A6.4A6.4A6.4A2$32.2A8.2A8.2A8.2A$
33.A8.A10.A8.A$31.A12.A6.A12.A$31.2A10.2A6.2A10.2A3$2.2A10.2A$.A2.A8.
A2.A$.A2.A8.A2.A$2.2A10.2A2$2.4A6.4A$.A4.A4.A4.A$2.4A6.4A2$2.2A8.2A$.
A2.A6.A2.A$2.2A8.2A19$2.2A8.2A18.2A10.2A$.A2.A6.A2.A16.A2.A8.A2.A$.A
2.A6.A2.A17.A2.A6.A2.A$2.2A8.2A19.2A8.2A2$2.4A6.4A17.4A6.4A$.A4.A4.A
4.A15.A4.A4.A4.A$2.4A6.4A17.4A6.4A2$2.2A8.2A19.2A8.2A$3.A8.A19.A2.A6.
A2.A$.A12.A18.2A8.2A$.2A10.2A2$33.2A10.2A$2.2A8.2A18.A2.A8.A2.A$.A2.A
6.A2.A18.A2.A6.A2.A$.A2.A6.A2.A19.2A8.2A$2.2A8.2A$32.4A6.4A$2.4A6.4A
15.A4.A4.A4.A$.A4.A4.A4.A15.4A6.4A$2.4A6.4A$32.2A8.2A$4.2A8.2A15.A2.A
6.A2.A$5.A8.A17.2A8.2A$3.A12.A$3.2A10.2A!

Re: Still life puzzles

Posted: July 4th, 2017, 1:36 pm
by wwei23
Red=too few neighbors, blue means that cell must be off, green means good to go. So far:

Code: Select all

x = 20, y = 19, rule = LifeHistory
4.BD2B$4.B2AB$4.BA2B3.4BD3B$4.BA3B2.D3AB2A2B$5B2A3B.D2BABABAB$D4A2BA
6BA2B2AB$BA2BABABA4B2A4BD$5BABABA2BA2B4AB$3.3BA2B4A2BA2BAB$4.3B2A4B2A
3BAB$5.3BAB2ABA3B2DB$5.D2BAB2ABA3B$5.2B2A4B2A3B$5.DA2B4A2BA3B$5.BA2BA
2BABABA2B$5.2B2A4BABABAD$6.2BDBD3BA2BAB$12.3B2A2B$13.2BD2B!
Two red cells with no neighbors have exactly three off neighbors, so we get this:

Code: Select all

x = 20, y = 19, rule = LifeHistory
4.BD2B$4.B2AB$4.BA2B3.4BD3B$4.BA3B2.D3AB2A2B$5B2A3B.D2BABABAB$D4A2BA
6BA2B2AB$BA2BABABA4B2A4BD$5BABABA2BA2B4AB$3.3BA2B4A2BA2BAB$4.3B2A4B2A
3BAB$3.BD3BAB2ABA3B2DB$3.B2A2BAB2ABA3B$3.BA2B2A4B2A3B$3.2B2A2B4A2BA3B
$4.2BA2BA2BABABA2B$5.2B2A4BABABAD$6.2BABA3BA2BAB$7.2B2AD3B2A2B$8.4B.
2BD2B!
Two red cells with two neighbors have one off neighbor, so we get this:

Code: Select all

x = 20, y = 19, rule = LifeHistory
4.BD2B$4.B2AB$4.BA2B3.4BD3B$4.BA3B2.D3AB2A2B$5B2A3B.D2BABABAB$D4A2BA
6BA2B2AB$BA2BABABA4B2A4BD$5BABABA2BA2B4AB$3.3BA2B4A2BA2BAB$3.D3B2A4B
2A3BAB$3.BA3BAB2ABA3B2DB$3.B2A2BAB2ABA3B$3.BA2B2A4B2A3B$3.2B2A2B4A2BA
3B$4.2BA2BA2BABABA2B$5.2B2A4BABABAD$6.2BABA3BA2BAB$7.2B3A3B2A2B$8.4BD
2BD2B!
There seems to be no more forcing.
EDIT:
I was wrong:

Code: Select all

x = 20, y = 19, rule = LifeHistory
4.BD2B$4.B2AB$4.BA2B3.4BD3B$4.BA3B2.D3AB2A2B$5B2A3B.D2BABABAB$D4A2BA
6BA2B2AB$BA2BABABA4B2A4BD$5BABABA2BA2B4AB$3.3BA2B4A2BA2BAB$3.D3B2A4B
2A3BAB$3.BA3BAB2ABA3B2DB$3.B2A2BAB2ABA3B$3.BA2B2A4B2A3B$3.2B2A2B4A2BA
3B$4.2BA2BA2BABABA2B$4.D2B2A4BABABAD$6.2BABA3BA2BAB$6.D2B3A3B2A2B$8.
4BD2BD3B!
EDIT:
Coolout Conjecture Counterexample, even if made internally stable:
Here red means bad cell.

Code: Select all

x = 20, y = 19, rule = LifeHistory
4.BA2B$4.B2AB$4.BA2B3.4BA3B$4.BA3B2.4AB2A2B$5B2A3B.A2BABABAB$5A2BA6BA
2B2AB$BA2BABABA4B2A4BA$5BABABA2BA2B4AB$3.3BA2B4A2BA2BAB$3.A3B2A4B2A3B
AB$3.BAD2BAB2ABA3B2AB$3.B2A2BAB2ABA3B$3.BA2B2A4B2A3B$3.2B2A2B4A2BA3B$
4.2BA2BA2BABABA2B$4.A2B2A4BABAB2A$6.2BABAD2BA2BAB$6.A2B3A3B2A2B$8.4BA
2BA3B!
Just checked LifeWiki for the puzzle of still lives where every cell has two neighbors, none for 9, 10, 11.
And Catagolue for 12, 13, none.

Re: Still life puzzles

Posted: July 22nd, 2017, 3:49 pm
by wwei23
BlinkerSpawn wrote:
muzik wrote:I'm pretty sure that the block is the only finite pattern at all with very cell having exactly 3 neighbours.
I also believe that the only stable patterns with every cell having 3 neighbors consist exclusively of blocks.
Here I will attempt to construct a pattern with every cell having 3 neighbors and containing no blocks.
Set your coordinate system so that the lower left corner of the pattern's bounding box is at (0,0), with coordinates increasing going up and to the right:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$D$D$10D!
Assume (0,0) is ON.
For the cell to have 3 live neighbors, (1,0), (0,1), and (1,0) must be ON, but then the pattern contains a block and is invalid, so (0,0) must be OFF:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$D$2A$CA8D!
Let's say (1,0) is ON instead.
There are four possible neighbors for (1,0): (0,1), (1,1), (2,1), and (2,0), but one of these must be (0,1) because the other three neighbors constitute a block. In addition, allowing (1,1) to be ON creates B3a at (0,0) so it is OFF and the other two neighbors must therefore be ON. Similar logic applies to (0,1), resulting in a ship:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$2C$C.C$B2C7D!
But (2,0) has two neighbors, and giving it a third causes (2,1) to have four neighbors and die, so this solution is also unworkable, and neither (1,0) nor (0,1) can be on in any solution. (This logic is reflection-invariant and so applies to both cases)
Let's force (2,0) to be ON, then.
By identical logic to the above we can immediately force these cells ON:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$D$BC.C$2B2C6D!
To prevent the contradiction in the previous case, though, (2,2) must stay OFF, forcing (1,1)'s two neighbors to be (2,1) and (2,0), creating B3a on (0,1). Therefore, (2,0) and (0,2) don't work either:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$2C$BC.C$2B2C6D!
Similarly, (3,0) creates this:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$B2C$B.C.C$3B2C5D!
(4,0) doesn't work:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$B$B3C$B2.C.C$4B2C4D!
This is the only way (5,0) can be done without creating birth at (2,1) or death at (3,2), but (1,1) and (1,2) are still unrescuable:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$B$B$B4C$BC2.C.C$5B2C3D!
And (6,0) has to be one of these but I don't know how to carry the logic past that:

Code: Select all

x = 30, y = 10, rule = LifeHistory
D19.D$D19.D$D19.D$D19.D$B19.B$B19.B$B19.B$B.4C14.B5C$B2C2.C.C12.B.C2.
C.C$6B2C2D10.6B2C2D!
I'm pretty sure some sort of proof-by-induction is possible along these lines.
If I could prove in each step that not just the end cells but each successive diagonal must be clear then the solution should just reduce to showing that each attempt to follow the instructions just creates the next level of ship and the proof would trivially follow from that and the logic used above.
Force (2,0) to be on:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$DB$D2B$10D!
4 possible arrangements:

Code: Select all

x = 70, y = 10, rule = LifeHistory
D19.D19.D19.D$D19.D19.D19.D$D19.D19.D19.D$D19.D19.D19.D$D19.D19.D19.D
$D19.D19.D19.D$D19.D19.D19.D$DB3A15.DB2A16.DBA.A15.DB.2A$D2BA16.D2B2A
15.D2B2A15.D2B2A$10D10.10D10.10D10.10D!
One on the right is a block so it doesn't count.
The others have a cell in common:

Code: Select all

x = 50, y = 10, rule = LifeHistory
D19.D19.D$D19.D19.D$D19.D19.D$D19.D19.D$D19.D19.D$D19.D19.D$D19.D19.D
$DB3A15.DB2A16.DBA.A$D2BA16.D2B2A15.D2B2A$10D10.10D10.10D!
Therefore:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$DBA$D2BA$10D!
Gray cannot be on because of B3a:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$DBAF$D2BA$10D!
Yellow has two other neighbors, they must both be on:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$DBAFA$D2BEA$10D!
3 arrangements:

Code: Select all

x = 50, y = 10, rule = LifeHistory
D19.D19.D$D19.D19.D$D19.D19.D$D19.D19.D$D19.D19.D$D19.D19.D$D2A17.DA.
A16.D.2A$DBAFA15.DBAFA15.DBAFA$D2B2A15.D2B2A15.D2B2A$10D10.10D10.10D!
First one causes B3a into blue, other two have cell in common:

Code: Select all

x = 30, y = 10, rule = LifeHistory
D19.D$D19.D$D19.D$D19.D$D19.D$D19.D$DA.A16.D.2A$DBAFA15.DBAFA$D2B2A
15.D2B2A$10D10.10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D2.A$DBAFA$D2B2A$10D!
Yellow cannot have 3 on neighbors because both would kill the one above it:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D2.A$DBAFA$D2BAE$10D!
Therefore (2,0) and (0,2) must be off:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$DB$DB$D3B$10D!
(1,1) must be off because it forces a block:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$DB2E$DBAE$D3B$10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$DB$D2B$D3B$10D!
(3,0):

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$DB$D2B$D3BA$10D!

Code: Select all

x = 70, y = 10, rule = LifeHistory
D19.D19.D19.D$D19.D19.D19.D$D19.D19.D19.D$D19.D19.D19.D$D19.D19.D19.D
$D19.D19.D19.D$DB18.DB18.DB18.DB$D2B3A14.D2B2A15.D2BA.A14.D2B.2A$D3BA
15.D3B2A14.D3B2A14.D3B2A$10D10.10D10.10D10.10D!

Code: Select all

x = 50, y = 10, rule = LifeHistory
D19.D19.D$D19.D19.D$D19.D19.D$D19.D19.D$D19.D19.D$D19.D19.D$DB18.DB
18.DB$D2B3A14.D2B2A15.D2BA.A$D3BA15.D3B2A14.D3B2A$10D10.10D10.10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$DB$D2BA$D3BA$10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$DB$D2BAF$D3BA$10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$DB$D2BAFA$D3B2A$10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$DB2.A$D2BAFA$D3B2A$10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$DB2.A$D2BAFA$D3BAE$10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$DB$DB$D2B$D4B$10D!
(2,1):

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$DB$DB$D2BA$D4B$10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$DB$DBA$D2BA$D4B$10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$DB$DBAF$D2BA$D4B$10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$DB2A$DBAFA$D2B2A$D4B$10D!
This is where it starts to deviate.
Gray would kill yellow:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D.3F$DBAE2F$DBAFEF$D2B2AF$D4B$10D!
Yellow needs one more neighbor and one is available:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D.3F$DBEA2F$DBAFAF$D2BAEF$D4B$10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$DA3F$DB2A2F$DBAFAF$D2B2AF$D4BA$10D!
But this causes B3j into blue:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$DE3F$DB2A2F$DBAFAF$D2B2AF$D4BE$10D!
Therefore (2,1) must be off.

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$DB$D2B$D3B$D4B$10D!
Also, the block theorem:

Code: Select all

x = 15, y = 5, rule = LifeHistory
7.D$8.D$B4.5D2.B$B7.D3.2B$3B4.D4.3B!
(4,0):

Code: Select all

x = 130, y = 10, rule = LifeHistory
D19.D19.D19.D19.D19.D19.D$D19.D19.D19.D19.D19.D19.D$D19.D19.D19.D19.D
19.D19.D$D19.D19.D19.D19.D19.D19.D$D19.D19.D19.D19.D19.D19.DB$DB18.DB
18.DB18.DB18.DB18.DB18.DB$D2B17.D2B17.D2B17.D2B17.D2B2.A14.D2B2.A14.D
2B$D3B16.D3BA15.D3BAF14.D3BAFA13.D3BAFA13.D3BAFA13.D3B$D4BA14.D4BA14.
D4BA14.D4B2A13.D4B2A13.D4BAE13.D5B$10D10.10D10.10D10.10D10.10D10.10D
10.10D!
(2,2):

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$DB$DB$D2BA$D3B$D5B$10D!
6 arrangements:

Code: Select all

x = 110, y = 10, rule = LifeHistory
D19.D19.D19.D19.D19.D$D19.D19.D19.D19.D19.D$D19.D19.D19.D19.D19.D$D
19.D19.D19.D19.D19.D$DB18.DB18.DB18.DB18.DB18.DB$DB3A15.DB2A16.DB2A
16.DBA.A15.DBA.A15.DB.2A$D2BA16.D2B2A15.D2BA16.D2B2A15.D2BA16.D2B2A$D
3B16.D3B16.D3BA15.D3B16.D3BA15.D3B$D5B14.D5B14.D5B14.D5B14.D5B14.D5B$
10D10.10D10.10D10.10D10.10D10.10D!
Also, the claw theorem:

Code: Select all

x = 15, y = 5, rule = LifeHistory
7.D$8.D$B4.5D.B$2B6.D2.2B$4B3.D3.4B!
Only 2 are valid:

Code: Select all

x = 30, y = 10, rule = LifeHistory
D19.D$D19.D$D19.D$D19.D$DB18.DB$DBA.A15.DBA.A$D2B2A15.D2BA$D3B16.D3BA
$D5B14.D5B$10D10.10D!
2 cells in common:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$DB$DBAFA$D2BA$D3B$D5B$10D!
2 arrangements, both equally valid for now:

Code: Select all

x = 30, y = 10, rule = LifeHistory
D19.D$D19.D$D19.D$D19.D$DB18.DB$DBAFA15.DBAFA$D2B2A15.D2BAF$D3BF15.D
3BA$D5B14.D5B$10D10.10D!
The first is object 3x2 43 and the second is object 3x3 337.
Object 3x2 43:
2 and 2 for yellow:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$DB2A$DBEFA$D2B2A$D3BF$D5B$10D!
Gray kills yellow:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D.3F$DBAE2F$DBAFEF$D2B2AF$D3BF$D5B$10D!
1 and 1 for yellow:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$DA3F$DBEA2F$DBAFAF$D2BAEF$D3BFA$D5B$10D!
B3j error:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$DA3F$DB2A2F$DBAFAF$D2B2AF$D3BFA$D5B$10D!
Object 3x2 43 invalidated.
Object 3x3 337:
2 and 2 for yellow:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$DB$DBEFA$D2BAF$D3BE$D5B$10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$DB2A$DBAFA$D2BAFA$D3B2A$D5B$10D!
Applied gray:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D.3F$DB2A2F$DBAFA2F$D2BAFAF$D3B2AF$D5B$10D!
1 and 1 for yellow:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$DA3F$DB2A2F$DBAFA2F$D2BAFAF$D3B2AF$D5BA$10D!
B3j error:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$DA3F$DB2A2F$DBAFA2F$D2BAFAF$D3B2AF$D5BA$10D!
Object 3x3 337 invalidated.
(2,2) must be off:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$DB$DB$D3B$D3B$D5B$10D!
Block theorem:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$DB$D2B$D3B$D4B$D5B$10D!
Claw theorem:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$DB$DB$D2B$D3B$D4B$D6B$10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$DB$D2B$D2B$D3B$D5B$D6B$10D!

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$DB$D2B$D3B$D4B$D5B$D6B$10D!
Ad infinitum. Proved.

Re: Still life puzzles

Posted: July 22nd, 2017, 9:45 pm
by BlinkerSpawn
I think there's an easier proof.
Say we've disproved a diagonal. We force the base of the next diagonal ON and build the claw using the same logic as the previous proofs:

Code: Select all

x = 21, y = 21, rule = LifeHistory
B2$B2$B2$B$B$B$B$B$2B$B.B$B2.B$B3.B$B4.B$B5.B$B6.B$B7.BA.A$B8.B2A$15B
.B.B.B!
But the corner of the claw needs another neighbor, and the only way to add one without causing a birth into blue is this way:

Code: Select all

x = 21, y = 21, rule = LifeHistory
B2$B2$B2$B$B$B$B$B$2B$B.B$B2.B$B3.B$B4.B$B5.B$B6.B$B7.BA.AE$B8.B2A$
15B.B.B.B!
But now the tip of the claw has the maximum three neighbors so the "wrist" of the claw must take neighbors as shown:

Code: Select all

x = 21, y = 21, rule = LifeHistory
B2$B2$B2$B$B$B$B$B$2B$B.B$B2.B$B3.B$B4.B$B5.B$B6.B2ED$B7.BAD2A$B8.B2A
$15B.B.B.B!
This forces B3a into blue so the base of the diagonal is OFF.
But the logic works the exact same way at the next location too:

Code: Select all

x = 21, y = 21, rule = LifeHistory
B2$B2$B2$B$B$B$B$B$2B$B.B$B2.B$B3.B$B4.B$B5.B2ED$B6.BAD2A$B7.B2A$B8.
2B$15B.B.B.B!
And at the next:

Code: Select all

x = 21, y = 21, rule = LifeHistory
B2$B2$B2$B$B$B$B$B$2B$B.B$B2.B$B3.B$B4.B2ED$B5.BAD2A$B6.B2A$B7.2B$B8.
2B$15B.B.B.B!
Notice that we are unable to start a ship-tie here.
We can, in fact, slide the claw all the way up, forcing every cell along the new diagonal OFF.
The "block theorem" finishes off the diagonal:

Code: Select all

x = 21, y = 21, rule = LifeHistory
B2$B2$B2$B$B$B$B2A$B2A$3B$B.2B$B2.2B$B3.2B$B4.2B$B5.2B$B6.2B$B7.2B$B
8.2B$15B.B.B.B!
Q.E.D.

Re: Still life puzzles

Posted: July 23rd, 2017, 11:01 am
by wwei23
This proof only works for things where there are no blocks. It may as well be an induction coil.
Here's my proof of the claw theorem:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$DB$D2B$10D!
Force a cell to be on:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$DB$D2BA$10D!
4 arrangements:

Code: Select all

x = 70, y = 10, rule = LifeHistory
D19.D19.D19.D$D19.D19.D19.D$D19.D19.D19.D$D19.D19.D19.D$D19.D19.D19.D
$D19.D19.D19.D$D19.D19.D19.D$DB3A15.DB2A16.DBA.A15.DB.2A$D2BA16.D2B2A
15.D2B2A15.D2B2A$10D10.10D10.10D10.10D!
Only one is valid:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$DBA.A$D2B2A$10D!
3 possible arrangements, first is invalid:

Code: Select all

x = 50, y = 10, rule = LifeHistory
D19.D19.D$D19.D19.D$D19.D19.D$D19.D19.D$D19.D19.D$D19.D19.D$D2A17.DA.
A16.D.2A$DBA.A15.DBA.A15.DBA.A$D2B2A15.D2B2A15.D2B2A$10D10.10D10.10D!
The other two have this in common:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D2.A$DBA.A$D2B2A$10D!
But the yellow cell cannot be stabilized without killing the light green cell:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D2.A$DBA.C$D2BAE$10D!
So the original cell must be off:

Code: Select all

x = 10, y = 10, rule = LifeHistory
D$D$D$D$D$D$D$DB$D3B$10D!
Block theorem says that the only available neighbors must make a block, so it must be off. Now, what about induction coils?

Re: Still life puzzles

Posted: July 23rd, 2017, 11:59 am
by AbhpzTa
WHITE CELL = ORIGIN , (X,Y)=(E-ward,N-ward)
non-block part : white cell = on
(SW edge of bounding diamond of non-block part : Y=-X)
(S-most ON cell on SW edge of bounding diamond of non-block part = origin)
blue area : no non-block part ...(a)
IF (1,0)(0,1)(1,1) are ON

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B$10B.2A$11BCA$13B$14B$15B$16B$17B$18B$19B$
20B$21B$22B!
white cell isn't in the non-block part
THEREFORE (-1,1) is ON

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B$10BA$11BC$13B$14B$15B$16B$17B$18B$19B$20B$
21B$22B!
IF (0,1) is ON

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B$10B2A$11BC$13B$14B$15B$16B$17B$18B$19B$20B$
21B$22B!
(-1,0)(-2,0)(-2,1)(-1,-1)(0,-1)(1,-1) are OFF

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B$9BF2A$9B2FC$10B3F$14B$15B$16B$17B$18B$19B$
20B$21B$22B!
blue area : ON cells = blocks (reason : (a))
anti B3a(-1,0)

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B$9BF2A$7B4FC$7BF2A3F$7BF2AF3B$7B4F4B$16B$17B
$18B$19B$20B$21B$22B!
anti B3q(-1,-1)

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B$9BF2A$7B4FC$7BF2A4F$7BF2AF2AF$7B4F2AFB$10B
4F2B$17B$18B$19B$20B$21B$22B!
anti B3n(-1,-3)

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B$9BF2A$7B4FC$7BF2A4F$7BF2AF2AF$7B4F2AFB$7BF
2A4F2B$7BF2AF6B$7B4F7B$19B$20B$21B$22B!
anti B3q(-1,-4)

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B$9BF2A$7B4FC$7BF2A4F$7BF2AF2AF$7B4F2AFB$7BF
2A4F2B$7BF2AF2AF3B$7B4F2AF4B$10B4F5B$20B$21B$22B!
... AD INFINITUM

THEREFORE (1,0)(1,1) are ON

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B$10BA.A$11BCA$13B$14B$15B$16B$17B$18B$19B$
20B$21B$22B!

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B$9BFAFA$9B2FCA$9B4F$14B$15B$16B$17B$18B$19B$
20B$21B$22B!
(anti B3k)

IF (-1,2)(-2,2) are ON

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B2A$9BFAFA$9B2FCA$9B4F$14B$15B$16B$17B$18B$
19B$20B$21B$22B!
(-3,1)(-3,2) are OFF

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$8BF2A$8B2FAFA$9B2FCA$9B4F$14B$15B$16B$17B$18B$
19B$20B$21B$22B!
anti B3a(-2,1) and (a)

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$8BF2A$6B4FAFA$6BF2A2FCA$6BF2A4F$6B4F4B$15B$16B
$17B$18B$19B$20B$21B$22B!
B3q ERROR

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$8BF2A$6B4FAFA$6BF2ADFCA$6BF2A4F$6B4F4B$15B$16B
$17B$18B$19B$20B$21B$22B!
THEREFORE (0,2) is ON

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B2.A$9BFAFA$9B2FCA$9B4F$14B$15B$16B$17B$18B$
19B$20B$21B$22B!

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B2.A2F$9BFAFAF$9B2FCAF$9B4F$14B$15B$16B$17B$
18B$19B$20B$21B$22B!

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B2.A2F$9BFAFAF$9B2FCAF$9B4FA$14B$15B$16B$17B$
18B$19B$20B$21B$22B!

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B2.A2F$9BFAFAF$9B2FCAF$9B4FA$12B2F$15B$16B$
17B$18B$19B$20B$21B$22B!
anti B3j(1,-1)

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B2.A2F$9BFAFAF$9B2FCAF$9B4FA$9BF2A2F$9BF2AF2B
$9B4F3B$17B$18B$19B$20B$21B$22B!
B3n ERROR

Code: Select all

x = 22, y = 21, rule = LifeHistory
B$2B$3B$4B$5B$6B$7B$8B$9B2.A2F$9BFAFAF$9B2FCAF$9BFD2FA$9BF2A2F$9BF2AF
2B$9B4F3B$17B$18B$19B$20B$21B$22B!
ONLY blocks are possible
QED

Re: Still life puzzles

Posted: July 23rd, 2017, 4:54 pm
by wwei23
Do still lives exist in B/S4 (None exist, what about B/S46?)?
Does an eater exist that can eat a glider, a lightweight spaceship, a middleweight spaceship, and a heavyweight spaceship?

Re: Still life puzzles

Posted: July 23rd, 2017, 7:07 pm
by dvgrn
wwei23 wrote:Do still lives exist in B/S4?
Interesting question. I don't immediately see how to turn a corner without resorting to an infinite agar, but there are enough possibilities that I can't instantly prove it's impossible:

Code: Select all

x = 32, y = 32, rule = B/S4:T32,32
15bo$15b2o$15b2o$16bo$16b2o$16b2o$16bo$16b2o$16b2o$16bo$15b2o$15b2o$
15bo$14b2o$3b2ob2o6b2o$11o4bob2o$2o7b6ob6o7b3o$12b2obo4b11o$15b2o6b2ob
2o$15b2o$15bo$14b2o$14b2o$14bo$13b2o$13b2o$14bo$13b2o$13b2o$14bo$14b2o
$14b2o!
#C [[ THUMBNAIL THUMBSIZE 2 ]]
wwei23 wrote:Does an eater exist that can eat a glider, a lightweight spaceship, a middleweight spaceship, and a heavyweight spaceship?
This one I think you need to be a little more specific about. Otherwise the answer is a trivial "yes". Gliders come in at a different angle from spaceships, so maybe you want to require that the first cell that interacts has to be the same in all four cases, or something like that?

Otherwise you can just weld together any glider eater, any LWSS eater, any MWSS eater, and any HWSS eater.

If you want the three *WSSes at least to use the same mechanism, here's a three-bait constellation that would work. Just have to add a factory to each of the signal outputs to rebuild one of the bait objects -- and then simply add a fishhook eater to eat a glider, or change your question to disallow that somehow.

Seems to me something better has been found for a universal *WSS signal converter since 2009, but I'm not finding it offhand, and it doesn't appear to be on the Big Converter List. Anyone have a link?

Re: Still life puzzles

Posted: July 23rd, 2017, 7:23 pm
by Apple Bottom
gameoflifeboy wrote:I've been searching B3/S2 for years to try to answer this. I'm already pretty sure the answer is "no", because the only available islands seem to be preblocks and rings of cells joined orthogonally or diagonally.
Could Simon Ekström's still life searcher be adapted to other CAs beyond Conway Life to answer this sort of question? It seems like a good tool for the job -- unfortunately the assumption that the rule worked with is B3/S23 seems to be baked fairly deeply into it, and I can't tell off-hand where.

Re: Still life puzzles

Posted: July 23rd, 2017, 9:44 pm
by dvgrn
dvgrn wrote:
wwei23 wrote:Do still lives exist in B/S4?
Interesting question... there are enough possibilities that I can't instantly prove it's impossible...

Code: Select all

x = 18, y = 18, rule = B/S4:T18,18
9bo$8bobo$7b5o$6b2o3b2o$5b2o5b2o$4b2o7b2o$3b2o9b2o$2b2o11b2o$b2o13b2o$
obo13bo$b2o13b2o$2b2o11b2o$3b2o9b2o$4b2o7b2o$5b2o5b2o$6b2o3b2o$7b5o$8b
obo!
#C [[ THUMBNAIL THUMBSIZE 2 ]]
It does look like there's an easy proof by contradiction here.

Consider the ON cell in a hypothetical still life that's farthest to the left along the top edge of the still life's bounding diamond (let's say). That cell (white) forces four ON cells below and to the right of it (green):

Code: Select all

x = 3, y = 2, rule = B/S4History
.CA$3A!
#C [[ THUMBNAIL ]]
But then the cell to the southwest (white, below) can't have four ON cells around it, without the cell to its right (yellow) getting overcrowded -- unless ON cells are added to the W, NW, or N, which contradicts the initial assumption:

Code: Select all

x = 3, y = 2, rule = B/S4History
..2A$.CEA$2A!
#C [[ THUMBNAIL ]]
Therefore there is no top edge of the still life's bounding diamond -- the hypothetical still life must be infinitely large. Q.E.D., right?

Re: Still life puzzles

Posted: July 24th, 2017, 1:41 pm
by praosylen
dvgrn wrote:Q.E.D., right?
I believe so.

It's also interesting to note that this disproves the existence of P1 photons in any 3D outer-totalistic rule in the logical extension of the Moore neighborhood containing B5 and none of B0234678 (B1 is disallowed for obvious reasons). The existence of higher-period photons would depend upon the existence of oscillators in 2D B5/S4. I suspect, but cannot prove at the moment, that they are impossible.

Re: Still life puzzles

Posted: July 24th, 2017, 4:28 pm
by wwei23
dvgrn wrote:
wwei23 wrote:Does an eater exist that can eat a glider, a lightweight spaceship, a middleweight spaceship, and a heavyweight spaceship?
This one I think you need to be a little more specific about. Otherwise the answer is a trivial "yes". Gliders come in at a different angle from spaceships, so maybe you want to require that the first cell that interacts has to be the same in all four cases, or something like that?
The XWSSes have to be on the same path. The glider must hit the same spot.

Re: Still life puzzles

Posted: July 24th, 2017, 5:21 pm
by dvgrn
wwei23 wrote:The XWSSes have to be on the same path. The glider must hit the same spot.
An eater with that constraint can almost certainly be built somehow -- or a multi-input converter, with the same signal output for any of the four inputs.

However, it would probably take several thousand ticks for the Giant Multi-Eater to recover after any meal. Mostly for that reason, nobody may actually want to complete a construction along these lines. It seems like the kind of thing that might remain forever in the "We Could If We Wanted To But It Would Be Big And Ugly" category.

If you want a reasonable-sized eater that recovers reasonably quickly, the answer might be "no" at the moment. But it's vaguely possible that some existing weird still lifes with very slow eater2-like action might be sufficiently omnivorous. Anyway, "yes" could possibly be only a Bellman search away.

One more question: does this glider

Code: Select all

x = 97, y = 24, rule = B3/S23
bo$2bo$3o7$11b2o$10bo2bo$10bo2bo$11b2o!
strike in the "same spot" as these *WSSes?

Code: Select all

x = 100, y = 100, rule = B3/S23
7bo$8bo$4bo3bo$5b4o$17b2o$16bo2bo$16bo2bo$17b2o$20$
7bo$8bo$3bo4bo$4b5o$17b2o$16bo2bo$16bo2bo$17b2o$20$
7bo$8bo$2bo5bo$3b6o$17b2o$16bo2bo$16bo2bo$17b2o!

Re: Still life puzzles

Posted: July 24th, 2017, 5:29 pm
by wwei23
dvgrn wrote:
wwei23 wrote:The XWSSes have to be on the same path. The glider must hit the same spot.
An eater with that constraint can almost certainly be built somehow -- or a multi-input converter, with the same signal output for any of the four inputs.

However, it would probably take several thousand ticks for the Giant Multi-Eater to recover after any meal. Mostly for that reason, nobody may actually want to complete a construction along these lines. It seems like the kind of thing that might remain forever in the "We Could If We Wanted To But It Would Be Big And Ugly" category.

If you want a reasonable-sized eater that recovers reasonably quickly, the answer might be "no" at the moment. But it's vaguely possible that some existing weird still lifes with very slow eater2-like action might be sufficiently omnivorous. Anyway, "yes" could possibly be only a Bellman search away.

One more question: does this glider

Code: Select all

x = 97, y = 24, rule = B3/S23
bo$2bo$3o7$11b2o$10bo2bo$10bo2bo$11b2o!
strike in the "same spot" as these *WSSes?

Code: Select all

x = 100, y = 100, rule = B3/S23
7bo$8bo$4bo3bo$5b4o$17b2o$16bo2bo$16bo2bo$17b2o$20$
7bo$8bo$3bo4bo$4b5o$17b2o$16bo2bo$16bo2bo$17b2o$20$
7bo$8bo$2bo5bo$3b6o$17b2o$16bo2bo$16bo2bo$17b2o!
Basically first interaction must be the same.

Re: Still life puzzles

Posted: July 24th, 2017, 5:44 pm
by dvgrn
wwei23 wrote:
dvgrn wrote:One more question: does this glider... strike in the "same spot" as these *WSSes?
Basically first interaction must be the same.
Hmm. Okay, that makes it a little tougher. Now I'm fairly sure that no such eater currently exists, and also that the easiest way to find one would be to build something very large that recovers very slowly.

If I had to construct one of these, I'd probably look for a small constellation that exploded when struck by any *WSS, as the pond does -- but that also exploded in a different way when struck by a glider (with the same initial interaction).

Then it's "just" a matter of adding catalysts to channel the two explosions, getting a different signal output in each case, and using each signal appropriately to send glider salvos back to clean up any leftover junk and rebuild the initial constellation.

It would certainly be much nicer to find a bait object that explodes the same way no matter what hits it, or even better a true four-way omnivorous eater -- generated by Bellman, let's say. But it seems as if that's likely to be a lot harder to find. Gliders just plain have a lot less "weight" behind them than the weightships do.

Re: Still life puzzles

Posted: August 6th, 2017, 12:45 pm
by mniemiec
wwei23 wrote:Do any still lifes exist from 9 to 19 cells so that every living cell has exactly two living neighbors and if not, then why(I've also apgsearched and turned up empty-handed.)?
No. I just did some searches in rule B3/S23 (where all still-lifes must necessarily be of that form), and the counts for various populations are:
4=1; 6=2; 7=1; 8=2; 20=4; 21=1; 22=34; 23=34; 24=57; 25=25; 26=97; 27=88; 28=165; 29=91; 30=129; 31=121; 32=265.

The reason there is a huge gap between 8 and 20 is that this constraint requires that all still-lifes be formed of one or more loops of living cells. This can be stable loops like beehives and ponds, unstable loops that require external stabilization, or L-trominos which also require stabilization. The smallest island that requires such stabilization is 8 bits (a long beehive) but that would require at least another copy of itself on both sides. A 10-bit long long beehive requires at least two beehives, for 22. A 12-bit long beehive can be supported by 2 tubs, for 20, but at that point, we already have the small lake.
wwei23 wrote:Other than some agars, is the block the only still life where every living cell has exactly three neighbors? If so, then why?
A brute-force search reveals none (other than the block) up to 36 bits. If you try to construct one manually, there are many that work as wicks or agars, but none appear to have finite stabilizations. It may be possible to prove this, although it appears that such a proof would be fairly complicated.

Some years ago, I went through a similar process for the rule B34/S34, in which P2 oscillators are plentiful, but the block appears to be the only still-life. I was able to show that other than the block, all still-lifes must necessarily have an exterior that consists of crenelations (straight lines with 1-bit protrusions every 2 or 3 cells), with Life ships or long ships at each corner. No other forms are possible. The smallest such still-life is 36 bits, and an exhaustive search did indeed find that one, plus one at 44; the next ones are two at 50 and one at 51.
All times are UTC-04:00
Page 1 of 2

Powered by phpBB® Forum Software © phpBB Limited