Difference between revisions of "Grandfather problem"
m |
|||
(2 intermediate revisions by one other user not shown) | |||
Line 9: | Line 9: | ||
|discoverer = mtve | |discoverer = mtve | ||
|discoveryear = 2016 | |discoveryear = 2016 | ||
|plaintext = true | |||
|rle = true | |rle = true | ||
}} | }} | ||
Line 15: | Line 16: | ||
:''Is there a configuration which has a father but no [[grandfather]]?'' | :''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 remained open until May 2016, when [[User:Mtve|mtve]] presented such a pattern.<ref name="mtve1" /> | Conway offered a $50 cash prize to "the first person to settle the grandfather problem either way". But the problem remained open until May 2016, when "[[User:Mtve|mtve]]" presented such a pattern.<ref name="mtve1" /> | ||
==Generation== | ==Generation== | ||
Line 27: | Line 28: | ||
==Verification== | ==Verification== | ||
mtve's discovery was confirmed to solve the grandfather problem by [[Matthias Merzenich]] with [[JLS]], using the following steps<ref name="sokwe" />: | "mtve"'s discovery was confirmed to solve the grandfather problem by [[Matthias Merzenich]] with [[JLS]], using the following steps<ref name="sokwe" />: | ||
# 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. | # 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. | ||
Line 96: | Line 97: | ||
}}</ref> | }}</ref> | ||
</references> | </references> | ||
[[Category:Patterns discovered by pseudonymous users]] |
Revision as of 23:40, 29 March 2019
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 remained open until May 2016, when "mtve" presented such a pattern.[2]
Generation
The pattern was found with the PicoSAT SAT solver, using an algorithm similar to the one employed by Nicolay Beluchenko's A196447:[3]
- 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[4]:
- 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.
- 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[5].
Next levels
"A father and grandfather, but no great-grandfather" pattern[6], and a "father, grandfather and great-grandfather, but no great-great-grandfather" pattern[7], have also been constructed by the same method.
No further levels have been found yet, but they almost certainly do exist.
Also see
References
- ↑ Robert Wainwright (October 1972). Lifeline, vol 6, p. 1.
- ↑ mtve (May 5, 2016). "Re: Thread for your unsure discoveries". ConwayLife.com forums. Retrieved on June 22, 2016.
- ↑ mtve (May 6, 2016). "Re: Thread for your unsure discoveries". ConwayLife.com forums. Retrieved on June 22, 2016.
- ↑ Matthias Merzenich (Sokwe) (May 6, 2016). "Re: Thread for your unsure discoveries". ConwayLife.com forums. Retrieved on June 22, 2016.
- ↑ mtve (June 2016). "Garden Of Eden 2G". Retrieved on July 8, 2016.
- ↑ mtve (June 2016). "Garden Of Eden 3G". Retrieved on July 8, 2016.
- ↑ mtve (December 12, 2016). "Garden Of Eden 4G". Retrieved on December 14, 2016.