Still life puzzles

For general discussion about Conway's Game of Life.
wwei23

Still life puzzles

Post by wwei23 » June 25th, 2017, 1:22 pm

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?
Last edited by wwei23 on August 6th, 2017, 1:15 pm, edited 3 times in total.

User avatar
muzik
Posts: 5578
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Still life puzzles

Post by muzik » June 25th, 2017, 2:00 pm

I'm pretty sure that the block is the only finite pattern at all with very cell having exactly 3 neighbours.

User avatar
BlinkerSpawn
Posts: 1992
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

Re: Still life puzzles

Post by BlinkerSpawn » June 25th, 2017, 2:58 pm

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.
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

Image

User avatar
muzik
Posts: 5578
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Still life puzzles

Post by muzik » June 25th, 2017, 3:34 pm

If such a pattern with exclusively 3 neighbours did actually exist, it would have to be big:

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

wwei23

Re: Still life puzzles

Post by wwei23 » June 25th, 2017, 4:23 pm

A pattern can contain a block, but it can't be JUST blocks.

drc
Posts: 1664
Joined: December 3rd, 2015, 4:11 pm

Re: Still life puzzles

Post by drc » June 25th, 2017, 4:35 pm

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!

wwei23

Re: Still life puzzles

Post by wwei23 » June 25th, 2017, 6:49 pm

The still life must be finite.

wwei23

Re: Still life puzzles

Post by wwei23 » June 27th, 2017, 9:51 am

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.
Last edited by wwei23 on July 6th, 2017, 5:49 pm, edited 2 times in total.

User avatar
gameoflifeboy
Posts: 474
Joined: January 15th, 2015, 2:08 am

Re: Still life puzzles

Post by gameoflifeboy » June 29th, 2017, 1:53 am

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!

wwei23

Re: Still life puzzles

Post by wwei23 » July 2nd, 2017, 12:32 pm

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!
Last edited by wwei23 on July 2nd, 2017, 1:42 pm, edited 3 times in total.

wwei23

Re: Still life puzzles

Post by wwei23 » July 4th, 2017, 1:36 pm

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.

wwei23

Re: Still life puzzles

Post by wwei23 » July 22nd, 2017, 3:49 pm

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.

User avatar
BlinkerSpawn
Posts: 1992
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

Re: Still life puzzles

Post by BlinkerSpawn » July 22nd, 2017, 9:45 pm

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.
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

Image

wwei23

Re: Still life puzzles

Post by wwei23 » July 23rd, 2017, 11:01 am

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?

AbhpzTa
Posts: 590
Joined: April 13th, 2016, 9:40 am
Location: Ishikawa Prefecture, Japan

Re: Still life puzzles

Post by AbhpzTa » July 23rd, 2017, 11:59 am

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
100009436650194649 = 94649 * 1056634900001

wwei23

Re: Still life puzzles

Post by wwei23 » July 23rd, 2017, 4:54 pm

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?
Last edited by wwei23 on August 6th, 2017, 1:16 pm, edited 1 time in total.

User avatar
dvgrn
Moderator
Posts: 10565
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Still life puzzles

Post by dvgrn » July 23rd, 2017, 7:07 pm

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?

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Still life puzzles

Post by Apple Bottom » July 23rd, 2017, 7:23 pm

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.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

User avatar
dvgrn
Moderator
Posts: 10565
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Still life puzzles

Post by dvgrn » July 23rd, 2017, 9:44 pm

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?

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Still life puzzles

Post by praosylen » July 24th, 2017, 1:41 pm

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.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

wwei23

Re: Still life puzzles

Post by wwei23 » July 24th, 2017, 4:28 pm

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.

User avatar
dvgrn
Moderator
Posts: 10565
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Still life puzzles

Post by dvgrn » July 24th, 2017, 5:21 pm

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!

wwei23

Re: Still life puzzles

Post by wwei23 » July 24th, 2017, 5:29 pm

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.

User avatar
dvgrn
Moderator
Posts: 10565
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Still life puzzles

Post by dvgrn » July 24th, 2017, 5:44 pm

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.

mniemiec
Posts: 1590
Joined: June 1st, 2013, 12:00 am

Re: Still life puzzles

Post by mniemiec » August 6th, 2017, 12:45 pm

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.

Post Reply