# Grandfather problem

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Grandfather problem
Pattern type Miscellaneous
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:

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

Although a 50\$ cash prize was offered by Conway, the problem remained open until May 2016, when 'mtve' presented such a pattern.[1]

## Generation

The pattern was found with Mark Owen's picosat, using an algorithm similar to the one employed by Nicolay Beluchenko's OEIS sequence A196447:[2]

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[3]:

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".

## References

1. mtve (May 5, 2016). "Re: Thread for your unsure discoveries". ConwayLife.com forums. Retrieved on June 22, 2016.
2. mtve (May 6, 2016). "Re: Thread for your unsure discoveries". ConwayLife.com forums. Retrieved on June 22, 2016.
3. Matthias Merzenich (Sokwe) (May 6, 2016). "Re: Thread for your unsure discoveries". ConwayLife.com forums. Retrieved on June 22, 2016.