Grandfather problem
Grandfather problem  
View static image  
Pattern type  Problem  

Number of cells  298  
Bounding box  24 × 23  
Discovered by  mtve  
Year of discovery  2016  
 

The grandfather problem is the following question, posed by John Conway in 1972 in Lifeline Volume 6,^{[1]} 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.^{[2]} This pattern ranked third place in the Pattern of the Year 2016 competition on the ConwayLife.com forums, behind the copperhead and the Caterloopillars.^{[3]}
Generation
The pattern was found with the PicoSAT SAT solver, using an algorithm similar to the one employed by Nicolay Beluchenko to discover A196447:^{[4]}
 Try setting the next cell on and off;
 Skip first level Gardens of Eden;
 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:^{[5]}
 Run a search to find all 1generation predecessors of mtve's pattern. Copy the cells that had the same setting in all solutions to the pattern.
 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.^{[6]}
22 × 22 grandfatherless pattern by mtve^{[6]} (click above to open LifeViewer) RLE: here Plaintext: here 
Next levels
"A father and grandfather, but no greatgrandfather" pattern^{[7]} and a "father, grandfather and greatgrandfather, but no greatgreatgrandfather" pattern^{[8]} 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 ntick predecessor but not an (n+1)tick predecessor.^{[9]} Furthermore, this pattern will fit in a box of diameter O(sqrt(log(n))).^{[10]}
References
 ↑ Robert Wainwright (October 1972). Lifeline, vol 6, p. 1.
 ↑ mtve (May 5, 2016). Re: Thread for your unsure discoveries (discussion thread) at the ConwayLife.com forums
 ↑ Alexey Nigin (June 3, 2017). Pattern of the Year 2016 (Results) (discussion thread) at the ConwayLife.com forums
 ↑ mtve (May 6, 2016). Re: Thread for your unsure discoveries (discussion thread) at the ConwayLife.com forums
 ↑ Matthias Merzenich (May 6, 2016). Re: Thread for your unsure discoveries (discussion thread) at the ConwayLife.com forums
 ↑ ^{6.0} ^{6.1} mtve (June 2016). "Garden Of Eden 2G". Retrieved on July 8, 2016.
 ↑ ^{7.0} ^{7.1} mtve (June 2016). "Garden Of Eden 3G". Retrieved on July 8, 2016.
 ↑ ^{8.0} ^{8.1} mtve (December 12, 2016). "Garden Of Eden 4G". Retrieved on December 14, 2016.
 ↑ Ilkka Törmä (January 6, 2022). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
 ↑ Adam P. Goucher (January 13, 2022). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
External links
 Grandfatherless at the Life Lexicon