Grandfather problem

Grandfather problem
x = 24, y = 23, rule = B3/S23 8ob5ob4ob3o$obo2b2o2b3o2b4ob2o2bo$2obob4ob4ob2obo2b3o$3obobobobo2bob3o b3o$ob2o6bo2b5o3b2o$bobob9obobo$obob2o4bo2bob4obo$obobo2b3ob3ob2o$4o2b 2ob3ob4o4bo$4ob6o2bo6bo$obob3ob2ob2ob3ob2o3bo$ob3obob6ob4obo$2b6obob2o 2b3o$2o2bobobob4o$b4ob4o2b6o4b2o$obobobo2b2ob2o2b2o2b3o$o3b2ob2o2b3ob 2o3bo$2ob2o4b2o4b3o$3obob5o3b4obobobo$ob4o2b2o3bobo4bo2bo$2ob2o4b2o3bo 5b2obo$b4obo2bobo4bob2o2b2o$3o3b2ob3o2bobo6bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ ZOOM 16 WIDTH 500 HEIGHT 500 ]]
View static image
Pattern type	Problem
Number of cells	298
Bounding box	24 × 23
Static symmetry	Unspecified
Discovered by	mtve
Year of discovery	2016
Glider synthesis Synthesis is not possible.
Pattern files Plaintext grandfatherproblemsolved.cells RLE grandfatherproblemsolved.rle

The grandfather problem is the following question, posed by John Conway in 1972 in Lifeline Volume 6, along with the unique father problem:

Is there a configuration which has a father but no grandfather?

Conway offered a $50 cash prize to "the first person to settle the grandfather problem either way". But the problem of a grandfatherless pattern remained open until May 2016, when mtve presented such a pattern. This pattern ranked third place in the Pattern of the Year 2016 competition on the ConwayLife.com forums, behind the copperhead and the Caterloopillars.

Generation

The pattern was found with the PicoSAT SAT solver, using an algorithm similar to the one employed by Nicolay Beluchenko to discover  A196447:

1. Try setting the next cell on and off;
2. Skip first level Gardens of Eden;
3. Choose the minimum number of grandparents, where "minimum number" is not the exact number but a minimal distance between first and last.

The final configuration has a total of 17920 parents, but no grandparents.

Verification

"mtve"'s discovery was confirmed to solve the grandfather problem by Matthias Merzenich with JLS, using the following steps:

1. Run a search to find all 1-generation predecessors of mtve's pattern. Copy the cells that had the same setting in all solutions to the pattern.
2. Mark all of unset cells with "X", increase the period by 1 and shift the pattern to the future by 1 generation. Set the outer cells to "X" in generation 0 and run another search, which eventually gives "Search finished: 0 solutions found".

Optimization

It is possible to reduce the size of this pattern by removing some cells, and also some other patterns with the same property exist.

x = 22, y = 22, rule = B3/S23 4o11bobob3o$2o2b2ob3o5bo3bobo$2obob4o2bobo3b3obo$obob4ob3o3bob2obo$ob 2ob2o4bob9o$ob3o2b4ob8obo$2ob3ob4o2bob3ob2o$3o2b3obobobobob2ob2o$2ob3o 4bo2bo2bobo2bo$obo2bobob3obo3bo3bo$2ob4obob7ob2o$bobobo3b3obobob3obo$ 7obobo4bo2b3o$b5obo2b8o$2bob2ob5o2bobob2o$o2b2obo2b5o2b3obo$3bob3ob3o 3b3obo$2b7o2b6obo$2b2ob2o3bob4ob3obo$o4bob6ob3obobo$obob3o3bobo2b3obob o$b2o3bob2o2bob2obo3bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBSIZE 2 ZOOM 8 ]]

22 × 22 grandfatherless pattern by mtve (click above to open LifeViewer)

Next levels

"A father and grandfather, but no great-grandfather" pattern, and a "father, grandfather and great-grandfather, but no great-great-grandfather" pattern, have also been constructed by the same method.

On January 6, 2022, Ilkka Törmä and Ville Salo solved a generalized version of the grandfather problem, proving that for every natural number n, there exists a pattern that has an n-tick predecessor but not an (n+1)-tick predecessor. Furthermore, this pattern will fit in a box whose diameter is equal to o(sqrt(log(n))).

External links

• Grandfatherless at the Life Lexicon